- ** Remove nodes on root to leaf paths of length < K. GFG
We do a postorder traversal and in each iteration we also path the length till node. When we reach a leaf node, we check if the length till that node is less then k. If true, delete it else don’t. So basically we start deleting the leaf node and keep moving up the tree.
The idea here is to use post order traversal of the tree. Before removing a node we need to check that all the children of that node in the shorter path are already removed.
There are 2 cases:
i) This node becomes a leaf node in which case it needs to be deleted.
ii) This node has other child on a path with path length >= k. In that case it needs not to be deleted.
- Find Count of Single Valued Subtrees. GFG Code
- *** Mirror of n-ary Tree. GFG Code
Algo: In an n-array we might have multiple children. We maintain these nodes in a child array. So in the main node class, there will be an array of child and a key variable. We follow the bottom up approach and start reversing this array of children.
- Find multiplication of sums of data of leaves at same levels. GFG
- **** Construct the binary tree from its parent array representation. Article GFG
Code Asked in Microsoft, Snapdeal
- Symmetric Tree (Mirror Image of itself). GFG Code
Algo: When can do a level order traversal. We dequeue two item from queue and check. We need to insert the nodes accordingly so that we can compare it.
Since we just dequeue the first two node and compare, the nodes should be inserted in the order in which we want to check for symmetry. Draw a example with 4 levels and check.
- **** Maximum Path Sum in a Binary Tree GFG
Algo: The max path can pass through the root or not. Code
Consider 20,2,1 –
For node 20, max path will be 20. For node 1, max path will be 1.
Now both the recursive call return to 2 with left = 20, right = 1. Now we need to check – if the max path – starts from 2 or start from 20 through 2 or from 1 through 2. So the first condition –
max_single = Math.max(Math.max(l, r) + node.data, node.data);
Now that we have found from which node will the max path begin (20, 2 or 1), we need to check if this subtree in itself is the max sum path ie. 20, 2, 1 form a max sum path. So second condition –
max_top = Math.max(max_single, l + r + node.data);
Now we decide the which is the max value, res.val stores max value
res.val = Math.max(res.val, max_top);
- Expression Tree – Given a postfix expression convert it into a tree, such that it can be evaluated using an inorder traversal. GFG
Algo: This can be done using a stack.
- Given a Binary Tree, change the value in each node to sum of all the values in the nodes in the left subtree including its own. GFG
- Iterative Search for a key ‘x’ in Binary Tree. GFG
Algo: Since it’s iterative use level order traversal
- ** Diagonal Sum of a Binary Tree. GFG
Algo: Do an inorder traversal passing the current diagonal just like we pass horizontal distance. Diagonal changes only when calling the left right and remains unchanged when calling the right child.
- In a Binary Tree, Create Linked Lists of all the nodes at each depth.
Code at Cracking the coding interview Logic
Algo: Do an in-order traversal. Create an arraylist of linked list for each level. Levels are always traversed in order so the first element will be at the starting of the linked list and will be added in correct order.