Bottom View of Binary Tree

Printing bottom view of Binary Tree


Category: Data Structure And Algorithms Tags: C#, Interview Question

Bottom view of Binary Tree Code Files

    Given a binary tree, print the nodes from left to right when it is seen from bottom. Given an example below:

Binary Tree
Fig 1: Binary Tree

 

If we look the tree from bottom we will be able to see 5, 15, 25 but we could see either 18 or 22 since overlapping on same height and we will not be able to see root 20 because 18 and 22 are in front of the root. So our solution will be 5, 15, 18, 25 or 5, 15, 22, 25.

Solution

If we consider root is the origin (0, 0) and try to allocate x and y coordinates to each node the picture will be as shown below:

Bottom view of Binary Tree
Fig 2: Bottom view of Binary Tree

 

Now we can see we have to pick node's in output which has highest height at each width. So we iterate each node starting from root, left nodes will have decrement in width by one from it's parent and right side of nodes will have increment in width by one from it's parent but height will be increasing by one in each iteration. Now let's write the code:

public class HashObject
{
public int Height { get; set; }
public BinarySearchTree.Node Node { get; set; }
}

Above a class stores a node with it's height.

/// <summary>
/// Traversing
/// </summary>
/// <param name="node">tree node</param>
/// <param name="dict">dictionary to hold lowest node at each width</param>
/// <param name="width">width from root</param>
/// <param name="height">height from root</param>
/// <returns></returns>
static Dictionary<int, HashObject> Traverse(BinarySearchTree.Node node, Dictionary<int, HashObject> dict, int width, int height)
{
if (node != null)
{
//left side width will decrese by one from root, but hieght always increases
Traverse(node.Left, dict, width - 1, height + 1);
if (!dict.ContainsKey(width))
{
dict.Add(width, new HashObject{ Height = height, Node = node});
}
else
{
//if stored height is less than current height at particular width
if (dict[width].Height < height)
dict[width].Node = node;
}
//right side width will increase by one from root, but hieght always increases
Traverse(node.Right, dict, width + 1, height + 1);
}
return dict;
}

Above method uses in-order traversal and inserting node with highest height at each width. We used dictionary's key as tree's height to make sure only one key is present for a particular width.

static void Main(string[] args)
{
//building tree
IBinerySearchTree bst = new BinerySearchTree();
bst.Insert(new Node() { Key = 20 });
bst.Insert(new Node() { Key = 15 });
bst.Insert(new Node() { Key = 18 });
bst.Insert(new Node() { Key = 25 });
bst.Insert(new Node() { Key = 22 });
bst.Insert(new Node() { Key = 5 });

Dictionary<int, HashObject> dict = new Dictionary<int, HashObject>();
dict = Traverse(bst.Root, dict, 0, 0);
//printing result
dict.ToList().ForEach(x => { Console.WriteLine(x.Value.Node.Key); });
Console.ReadLine();
}

Output:

5
15
18
25


Like 0 People
Last modified about 24 days ago
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 125
Questions: 9
Given Best Solutions: 8 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x