# Binary Tree – Set 2

1, 4-6, 8, 10, *11, 14, 15, 18, 21, 22, **23, 24, 29, 34, 35, 36,

1. *** Populate Inorder Successor for all nodes GFG Code
Algo:
1. Traverse the given tree in reverse in-order traversal(this is visiting the right most node -> root -> left ) and keep track of previously visited node. When a node is being visited, assign previously visited node as next. Draw a tree and write down it’s in-order traversal and it’s result to first visualize the o/p.
the next pointer gets updated when we are done with the right subtree everytime, even if it’s a leaf node.
Time Complexity: O(n)
2. This is also referred to as Threaded Binary Tree. GFG Simple Code
The same can be easily implemented using queue.We first do an inorder traversal of the tree and store it in a queue (we can use a simple array also) so that the inorder successor becomes the next node. We again do an inorder traversal and whenever we find a node whose right is NULL, we take the front item from queue and make it the right of current node. We also set isThreaded to true to indicate that the right pointer is a threaded link. GFG solution is unnecessarily complicated. Code
Read about Threaded Binary Tree here. The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists). Check the code for inorder traversal using the concept.

2. Convert a given tree to its Sum Tree – Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0. GFG Code

3. Vertical Sum in a given Binary Tree – Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
GFG Code
Algo: We need to check the Horizontal Distances from root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
We can do inorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1.
We use hashmap because as hd will be negative and so array can’t be used(no negative array index).

4. *** Print a Binary Tree in Vertical Order. Code GFG
Algo: The basic concept is same as the above question. GFG has over complicated the solution in this case. We only need to traverse the tree once and store all the nodes at each horizontal distance is a map. Then print the map. Since we want the horizontal distance to displayed in order we will need to use TreeMap.Java TreeMap class implements the Map interface by using a tree. It provides an efficient means of storing key/value pairs in sorted order.

5. ** Given a Binary Tree, find the maximum sum path from a leaf to root. GFG Code
We need to print the maximum path as well.
Algo:
We use the logic for printing the nodes from root to leave node. Since in that we save the entire path for all possible route that will use a lot of space. We  modify that code to pass the maximum sum as int instead of passing array/arraylist (this will be done instead of printing the array) . Also we would need to store the  node where we found the max value.
Since it the above case we used to print the entire path, but here we are not storing that. So we will have to write a method to print all nodes from root to the target node. This can be seen in the code link here.

6. *** Check whether a binary tree is complete or not. Article. Code. GFG
Algo:
– A binary tree is a complete binary tree if all levels of the tree starting from root node level are filled.
– Only the last level of the tree is allowed to have an incompletely filled state.
– Also for tree to be a complete binary tree, all nodes should be placed as left as possible.

7. Check whether a binary tree is a full binary tree or not – A full binary tree is defined as a binary tree in which every node other then the leave node has two children (SO). Conversely, there is no node in a full binary tree, which has one child node. GFG
Algo: A full binary tree is a tree in which every node other than the leaves has two children. So just check for this condition. Except the root node, all other nodes will have two children.
If left is null and right is not null or vice-verse for non-leaf node it’s not a full binary tree.

8. **** Boundary Traversal if binary tree. GFG. Code . Article
Algo:
We need to print the left boundary, right boundary and other nodes separately. All can’t be handled in a single loop. See the code comments for pitfalls.
So we start with printing the left boundary top-down manner. Print all the leaf nodes(to avoid printing duplicates leaf nodes, we don’t print leaf nodes, while printing left and right boundary). Then print all the leaf nodes. Then print the right boundary bottom-up manner.

9. Reverse Level Order Traversal. GFG
Code is simple and same as in GFG.
Algo: Use queue and stack. We can easily modify the  queue logic of level order traversal. Instead of poping a value we add it to a stack. So the first element that was originally printed is pushed to bottom to stack and the last element is at the top of stack.
Since we need to print the level in order left to right, we shd push the value accordingly. So we push the right node before left node, this way left node is poped before right node and the level order is also maintained.

10. Extract Leaves of a Binary Tree in a Doubly Linked List. GFG Code
Also check (GFG)
Algo: We need to traverse all leaves and connect them by changing their left and right pointers. We also need to remove them from Binary Tree by changing left or right pointers in parent nodes.  In the following implementation, we add leaves at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order.
Time Complexity: O(n)
This problem and the problem below are based on different concept. Here we are extracting a ddl out of leaf node of a tree(at the end we have a ddl and a modified tree). In the below problem we convert a bt to a ddl in place.

11. **** Convert a given Binary Tree to Doubly Linked List. Code GFG
Algo: We need to maintain a head that points to the first element in the inorder traversal. And we need to maintain a prev node which is used to set the prev of the DDL.
If we do a inorder recursive traversal then first time both left and right are called is in the left most leaf node(here). So here we find our head DLL. Now we need to maintain the prev node so that we can connect the left of next node(which is prev in DLL) in the inorder traversal to it. We are changing setting left and right node here

12. ** Construct Complete Binary Tree from its Linked List Representation – GFG Read full question details on GFG.
Algo: The idea is to do Level order traversal of the partially built Binary Tree using queue and traverse the linked list at the same time.
We will use queue for this.
So to start we create a node with the data from the head of LL to the queue. Then we start traversing the linked list until it’s empty. We take two item(if they exists) from the LL and create two tree Node. Then dequeue the Node from  queue and add these newly created Nodes as it’s left and right child. Now add these right and left child to end of queue.

13. * Difference between sums of odd level and even level nodes of a Binary Tree. GFG. Asked in Amazon
The solution given on GFG is awesome, but personally that not easy to come up in an interview.
Algo:
1. Use level order traversal. We keep track of the level and update the sum accordingly for each node level wise.
2. We can do it recursively using preorder traversal. At each recursive call we pass the current sum and the level. We update the result accordingly. C++ Code

14. Construct a Binary Tree from Postorder and Inorder. GFG
Algo: Same logic as to construct a tree from preorder and inorder (GFG). The only diff is the in preorder the root will be at the end. So we first find the root element from the end and then find that element’s position in inorder and split inorder based on that index.

15. Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.
GFG
Algo: This approach is completely based on the logic to construct a tree using inorder and preorder traversal are given. Instead of creating we just print these. The logic is same. Code .
The printing things works because first the left most node is formed and then the right most node and so on…and postorder is left, right and root….

16. Find depth of the deepest odd level leaf node. GFG
Algo: We can do it simply using recursion. Just keep passing the level and return the max level. We can also do it via level order traversal

17. Given a Binary Tree, check if all leaves are at same level or not. GFG Link
Algo:
– Basically we have to check that, (the first leaf node is seen at the start of a level) AND (All the nodes after the first leaf node should also be leaf nodes)

18. *** Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. GFG
Algo:
1. We can use level order traversal and print the first node in every level.
2. We can  do this using preorder traversal. We need to print only one node per level. So we need to keep track that the level that has been printed yet or not.
We can do this using a hashset or we can use a single variable in this case. We create a variable which indicates the maximum level that has been printed till now. So if the level is greater than the maximum level that has been printed don’t print that level else print the level and update the maximum.

19. Deepest left leaf node in a binary tree. GFG
Algo:
– Recursively traverse the tree and keep track of the deepest node seen.
We need to pass around result node, max level node and current level.
Check the GFG code for level class logic, which comes handy in many question using recursion. (since we can’t pass around a integer via reference, we create a class(private class should be a good candidate here), and then pass it around).
– We can also do it via level order traversal.

20. Find next right node of a given keyGFG
Algo:
1. Level Order Traversal. The solution on GFG has been complicated.  The thing to note here is that, it’s easy to check if the value is matched when we are dequeue value from the queue. This is because the immediate next value, in the queue is the one that might be the solution. We need to keep the level in consideration when checking.
2. Preorder traversal. Here we only need to include the key on the same level else it won’t work.  When we find the key we get it’s level. Then we move right and print the node on the same level.

21. * Given a binary tree, find the distance of given node from the root. Code
GFG  Note: Distance is the number of edges b/w given node and the root. Should clarify it in an interview as some consider the nodes b/w given node and root(both included).

22. * Sum of all the numbers that are formed from root to leaf paths. GFG
Algo: The idea is to do a preorder traversal of the tree. Here we don’t need to pass around an array. We can keep passing the sum till the node, before we split the path at left/right node.
In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.

23. ***** Lowest Common Ancestor in a Binary Tree – Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor.  GFG Code
Algo: We need to do a preorder traversal and keep track of which subtree return that both n1 and n2 are found. (In the code I wrote I was passing boolean to keep track but we will have to pass the node as we need to print the node data finally).
The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
We need to handle the case that both are present in the tree as well.

24. **** Given two nodes in a binary tree, find the dis­tance between them. GFG. Article Code
Algo:
Distance(X, Y) = Distance(root, X) +Distance(root, Y) — 2*(Distance(root to LCA(X,Y)

25. ** Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. GFG Microsoft
Algo: This is a problem that uses similar logic to printing all ancestor of a leave node( Q10 in set1 GFG  Code or q22 set 1 Code).
The first one stores the entire path for each path and prints it when it hits a leave node. The other is a recursive method to find and print all nodes.
Here we  can use can use the first approach easily. Just build up the array path from root to leave and when we find a leave root, and print the element at n – k -1 position where n is the total element in the path and -1 because we need to exclude the leave element as it also included in that array generated. We will have to keep track what node has already been printed. We can either have an array or use a hashset if all node elements are unique.

26. [Pending] Print all nodes at distance k from a given node.  GFG

27. *** Construct a binary tree from given Inorder and Level Order Traversal
GFG –
We can stick to GFG solution
Algo: The first element in the level order will be root. We search for this root element in inorder. This divides inorder into two part – left and right. Now we need to search for the first element in level order in the left and right part of the sub-array created above. O(n^3) – worst case.

28. Find the maximum sum leaf to root path in a Binary Tree. GFG
Algo: We need to find the path from root to leaf which has maximum sum. So will have to find all the sum, and the compare it and then print the path.
So in these type of questions we can easily see that we need the entire path. So we need to store the entire path while traversing. Here we have two options. Either we can pass the entire path in an array or just pass a variable which keeps track of the maximum sum and max node. Passing an array is expensive in terms of space. If we know the leaf node, then we can traverse the entire tree again(O(n)) and print the leaf to root path. So it’s a tradeoff. The thing to notice here is that we have two choice here.

29. * Reverse alternate levels of a perfect binary tree. GFG
Algo:
– Do an inorder traversal and store all the odd level node data in an array. Then reverse the array. Again do a inorder and replace the value at each odd level node with the value in the array. Basically we are replacing the value and not changing the link.
– We can also do a level order traversal. So all the odd level node in an array and then reverse the node value.
Better Solution   O(1) space complexity and O(n) time complexity.

30. Given the binary Tree and the two nodes say ‘a’ and ‘b’, determine whether the two nodes are cousins of each other or not. GFG
Two nodes are cousins of each other if they are at same level and have different parents.
Algo: The idea is to find level of one of the nodes. Using the found level, check if ‘a’ and ‘b’ are at this level. If ‘a’ and ‘b’ are at given level, then finally check if they are not children of same parent. Find the level of both nodes given. While finding the level also find the parent of both the nodes.
We can do a in-order traversal. When we find the nodes with the value, we save it’s level and parent. At the end compare these values.

31. ***** Serialize and Deserialize a Binary Tree – GFG, Article, Code
Algo:
We can store the preorder of a binary tree and then regenerate the entire tree from this( This is possible only if we mark the leave node as well in the preorder. So when we store preorder we store the leave node node as null. This helps us to regenerate the tree just using the preorder which is otherwise not possible)
–  If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.
– For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.
–  A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.
– A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree. A simple way to optimize it by just storing the preorder traversal with the value for all null nodes marked.
So this will require storing n+1 marker for n keys. This can be further optimized by using only a single bit to mark the internal and external node and single bit to mark null.
Similar: Succinct Encoding of Binary Tree GFG
Same logic as above.

32. Given a binary tree and two level numbers ‘low’ and ‘high’, print nodes from level low to level high. GFG
Algo:
Simple level order traversal

33. [Pending] *** Given a Binary Tree and a key ‘k’, find distance of the closest leaf from ‘k’. GFG
Algo:

The main point to note here is that a closest key can either be a descendent of given key or can be reached through one of the ancestors.
The idea is to traverse the given tree in preorder and keep track of ancestors in an array. When we reach the given key, we evaluate distance of the closest leaf in subtree rooted with given key. We also traverse all ancestors one by one and find distance of the closest leaf in the subtree rooted with ancestor. We compare all distances and return minimum.

34. ** Print Nodes in Top View of Binary Tree  Optimization
Algo: We need to print the nodes on the basis of horizontal level. If the node on that particular level has not been yet printed then it is a part of top view(as when viewed from top, only one node at the top of a hd will be visible). So we can do a level order traversal to print the nodes in order or use preorder traversal. To keep track if a node has been already printed we can use a hashset. Other way to achieve this is to maintain two pointers, left  and right. At any particular level we print only if the given hd for a node is smaller then the left or greater than right. Update left and right accordingly.
Same logic used here – ** Print a Binary Tree in Vertical Order

35. ** Bottom View of a Binary TreeGFG
Algo: We will have to do a level order traversal here. I couldn’t come up with a recursion solution.  The following are steps to print Bottom View of Binary Tree.
1. We put tree nodes in a queue for the level order traversal.
2. Start with the horizontal distance(hd) 0 of the root node, keep on adding left child to queue along with the horizontal distance as hd-1 and right child as hd+1.
3. Also, use a TreeMap which stores key value pair sorted on key.
4. Every time, we encounter a new horizontal distance or an existing horizontal distance put the node data for the horizontal distance as key. For the first time it will add to the map, next time it will replace the value. This will make sure that the bottom most element for that horizontal distance is present in the map and if you see the tree from beneath that you will see that element.
(every node also has a hd value in the Node structure. In recursion we could easily pass the hd but here we are updating the node value similarly. Instead of passing the node value we save it in the node and use it when it’s popped from queue).

36. ** Perfect Binary Tree Specific Level Order Traversal. GFG
Algo:
1. We can do standard level order traversal here too but instead of printing nodes directly, we have to store nodes in current level in a temporary array or list 1st and then take nodes from alternate ends (left and right) and print nodes. Keep repeating this for all levels.
2. Need to recognize the pattern and then it’s simple level order traversal.
The standard level order traversal idea will slightly change here. Instead of processing ONE node at a time, we will process TWO nodes at a time. And while pushing children into queue, the enqueue order will be: 1st node’s left child, 2nd node’s right child, 1st node’s right child and 2nd node’s left child

37. Convert left-right representation of a binary tree to down-right. GFG. Article
Algo: The idea is to traverse the tree in postorder fashion and for every node
– If its left child is empty, then make its right child as left and set right to null.
– If left child already exists, then make right child of its left child to point to its right child and set right child to null.
We set the right child to be parents right child. We link the right node of the current node, to the child’s right node. In this case we will set the current right node as null.
Since we need to make the right pointer of current node to it’s left child’s right child, we need to make sure that it’s left child’s right is null.

38. [Pending] Minimum no. of iterations to pass information to all nodes in the tree. GFG Asked in Amazon

39. Given a binary tree,remove all the half nodes – Code GFG
Algo: The idea is to use post-order traversal to solve this problem efficiently. We first process the left children, then right children, and finally the node itself. So we form the new tree bottom up, starting from the leaves towards the root.

40. *** Clone a Binary Tree with Random Pointers – This is similar to cloning a linked list with random pointer(GFG). The same hash logic can be applied here. GFG

41. Find sum of all left leave in a binary tree. GFG

42. Delete in binary tree. GFG