BT Set – 2, BT Set – 1, Question Set (101- ..)

Binary Tree Visualizer

**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:

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
- In a Binary Tree, Create Linked Lists of all the nodes at each depth.

**Algo:**Code at Cracking the coding interview Logic

Advertisements