Recently I had given interview in Morgan Stanley for Senior Java Developer profile, the intervier asked me, we have a balanced Binary Tree, am trying to throw a light from a particular node, which all nodes will be visible?
I tried my best, but failed to write an algorithm. After the interview I realized he was asking to write an algorithm to see the bottom view of a Binary Tree.
The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.
If we see the tree from bottom from a particular node, which all nodes will be visible is the bottom view of a Binary Tree.
The bottom view of above Binary Tree is: 7, 5, 8, 6
Before writing the algorithm to find the bottom view, let us first understand how horizontal distance is calculated:
Horizontal distance of the root = 0
Horizontal distance of a left child = horizontal distance of its parent - 1
Horizontal distance of a right child = horizontal distance of its parent + 1
ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST
Algorithm To Get The Bottom View Of Binary Tree
1). We need to follow vertical order traversal to calculate the Horizontal Distance (Please Check: Vertical Order Traversal and Level Order Traversal).
2). We will have a Hash Table, which contain HD and the Nodes associated with that HD.
3). Bottom view would the node appearing last in each set of HashTable is the Bottom View.
For the this Binary Tree, HashTable will contain:
-3: h
-2: d
-1: b, i
0: a, e, f
1: c, j
2: g
3: k
FYI, the Level Order Traversal is abcdefghijk. For HD=0, there are three nodes a, e and f. We need to add these nodes in the HashTable in the order they appear in Level Order Traversal.
Bottom View would be: h,d,i,f,j,g,k or h,d,i,e,j,g,k.
Since e and f are at same level and have same HD, anyone can be used in the bottom view.
-K Himaanshu Shuklaa..
I tried my best, but failed to write an algorithm. After the interview I realized he was asking to write an algorithm to see the bottom view of a Binary Tree.
The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.
If we see the tree from bottom from a particular node, which all nodes will be visible is the bottom view of a Binary Tree.
Before writing the algorithm to find the bottom view, let us first understand how horizontal distance is calculated:
Horizontal distance of the root = 0
Horizontal distance of a left child = horizontal distance of its parent - 1
Horizontal distance of a right child = horizontal distance of its parent + 1
ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST
Algorithm To Get The Bottom View Of Binary Tree
1). We need to follow vertical order traversal to calculate the Horizontal Distance (Please Check: Vertical Order Traversal and Level Order Traversal).
2). We will have a Hash Table, which contain HD and the Nodes associated with that HD.
3). Bottom view would the node appearing last in each set of HashTable is the Bottom View.
-3: h
-2: d
-1: b, i
0: a, e, f
1: c, j
2: g
3: k
FYI, the Level Order Traversal is abcdefghijk. For HD=0, there are three nodes a, e and f. We need to add these nodes in the HashTable in the order they appear in Level Order Traversal.
Bottom View would be: h,d,i,f,j,g,k or h,d,i,e,j,g,k.
Since e and f are at same level and have same HD, anyone can be used in the bottom view.
-K Himaanshu Shuklaa..
No comments:
Post a Comment