Binary Tree

Guide

Basic Traversal	3
Easy warm-ups	6
BST variations	5
Mediums	7
Waste	2

Basic traversals

‼️In-order

Recursion Easy

O(n) time and space

Iterative

• Remember how neetcode did the traversal

Pre-order

Recursion

Iteration - The usual stack thing

• put right in stack (for later processing)

Post-Order

Recursion

Iteration

single-stack iterative post-order traversal reversing output of a DFS which processes right child first than left child gives back post order

function postorderTraversal(root) {
  const result = [];
  const stack = [];
 
  if (root) stack.push(root);
 
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);
 
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
 
  return result.reverse();
}
 

Easy warm-ups(6):

• Invert binary tree

• max Depth of tree

• ⭐diameter problem is actually a DFS findHeight problem

• ⭐balanced binary tree - DFS. pair return from every node (balanced? and height)

  • Or: use a global variable:

• same tree - easy

• Subtree of another tree: uses same tree

---

BST Variations (5)

• BST LCA - easy
• ⭐BST insert - First problem to mug-up
  • there can be multiple solutions
  • Both recursion as well iterative

    Recursion : O(h) time and space - h is height

    

    Iteration O(n) time, O(1) space

    
• ⭐BST deletion - First problem to watch again
  • Root may change
  • 3 Conditions to worry about: https://www.youtube.com/watch?v=DkOswl0k7s4
    • Deleting a leaf node
    • deleting node with 1 child
    • deleting node with 2 children
      • from the right side, take minimum node value - assign to node and delete value from right side (see below)
      • OR, from left side, take maximum node value - assign to node and delete value from left side.
• BST validation
  • BST - root value is larger than “every value of left tree”
  • and root value is smaller than “every value of right tree”
  • lower bound and upper bound
• BST In Order & kth smallest
  • BST In order traversal gives the sorted array of its value

Medium Probs (7)

• Binary Tree level order traversal - easy
• Binary Tree right side view - easy
• Good Nodes - good problem
  • Usual DFS with a “cap value”
  • linear solution
• ⭐Delete Leaves With a given value - good question
  • Root might get changed
  • Root.left & root.right might get changed
• House Robber 3 pattern:
  • how to pass on parental decisions to child
  • withRoot, withoutRoot comb
• ⭐Construct Binary Tree From Preorder And Inorder Traversal of distinct element tree
  • Read its optimal solution code (video code is o(n^2) - but optimal is o(n))
  • Reconstructing Binary Tree by traversals arrays
  • o(n^2) code : its n^2 because indexOf and slice is being called in every recursive calls which itself is o(n)
• Binary Tree Maximum path sum
  • Classic!
  • close to diameter problem

Waste Problems (2)

• Construct Quad Tree - Most odd question
  • Read how we calculated its time complexity
• Serialize and Deserialize

  	if (node === null) {
          res.push('N');
          return;
      }

# Other practice questions

1. Find minimum value in BST

```js
	function findMin(node) {
	  while (node.left) {
	    node = node.left;
	  }
	  return node.val;
	}

2. Find max value in BST

 
	function findMax(node) {
	  while (node.right) {
	    node = node.right;
	  }
	  return node.val;
	}