Binary Tree – Set 3


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

  1. 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.


  2. Find Count of Single Valued Subtrees. GFG Code

  3. *** 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.


  4. Find multiplication of sums of data of leaves at same levels. GFG
  5. **** Construct the binary tree from its parent array representation. Article GFG
    Code Asked in Microsoft, Snapdeal
  6. 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.
  7. **** Maximum Path Sum in a Binary Tree GFG
    Algo: The max path can pass through the root or not.  Codetree4
    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);


  8. 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.


  9. 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 

  10. Iterative Search for a key ‘x’ in Binary Tree. GFG
    Algo:Since it’s iterative use level order traversal
  11. Diagonal Sum of a Binary Tree. GFG
  12. In a Binary Tree, Create Linked Lists of all the nodes at each depth.
    Algo: Code at Cracking the coding interview Logic
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s