- Remove nodes on root to leaf paths of length < K. GFG
Algo: 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: We just need to check if in the left subtree and right subtree, left and right keys are same. So we need to traverse the tree recursively in two part.
- **** 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