Tree Fundamentals

🌳 Binary Trees: The Family Tree of Data

Imagine you’re looking at your family tree. At the top is your great-grandparent, then your grandparents, then your parents, then you and your siblings. That’s exactly how a binary tree works!

🏠 Binary Tree Fundamentals

What is a Binary Tree?

Think of a binary tree like an upside-down family tree. At the very top, there’s ONE person (we call them the root). Each person can have at most 2 children - a left child and a right child.

Simple Example:

       👴 Grandpa (Root)
      /         \
   👨 Dad      👩 Aunt
   /    \         \
 👦 You  👧 Sis   👶 Cousin

The Rules:

• Every tree has ONE root (the top person)
• Each person (node) can have 0, 1, or 2 children
• Each child has exactly ONE parent

In Code (JavaScript):

class TreeNode {
  constructor(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }
}

// Build a simple tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

graph TD
    A["1 Root"] --> B["2 Left"]
    A --> C["3 Right"]

Key Terms to Remember:

• Root: The topmost node (like the oldest ancestor)
• Leaf: A node with NO children (the youngest generation)
• Parent/Child: The connection between nodes
• Sibling: Nodes sharing the same parent

🚶 Tree Traversal Techniques

How Do We Visit Everyone in the Family?

Imagine you want to say “Hi” to everyone in your family tree. There are three special ways to do this!

1. In-Order Traversal (Left → Root → Right)

The Rule: Always visit the left side first, then the parent, then the right side.

Think of it like reading a book: left page, middle, right page!

function inOrder(node) {
  if (node === null) return;
  inOrder(node.left);      // Visit left
  console.log(node.val);   // Visit current
  inOrder(node.right);     // Visit right
}

graph TD
    A["2"] --> B["1"]
    A --> C["3"]
    style B fill:#90EE90
    style A fill:#FFD700
    style C fill:#87CEEB

Order visited: 1 → 2 → 3 (Left, Root, Right)

2. Pre-Order Traversal (Root → Left → Right)

The Rule: Visit yourself FIRST, then your children.

Like a boss checking in: “I’m here! Now let me see my team.”

function preOrder(node) {
  if (node === null) return;
  console.log(node.val);   // Visit current FIRST
  preOrder(node.left);     // Then left
  preOrder(node.right);    // Then right
}

Order visited: 2 → 1 → 3 (Root, Left, Right)

3. Post-Order Traversal (Left → Right → Root)

The Rule: Visit all children FIRST, then yourself last.

Like a teacher grading papers: check all student work before giving the final grade!

function postOrder(node) {
  if (node === null) return;
  postOrder(node.left);    // Visit left first
  postOrder(node.right);   // Then right
  console.log(node.val);   // Visit current LAST
}

Order visited: 1 → 3 → 2 (Left, Right, Root)

4. Level-Order Traversal (BFS)

The Rule: Visit everyone floor by floor, like taking the elevator!

function levelOrder(root) {
  if (!root) return [];
  let queue = [root];
  let result = [];

  while (queue.length > 0) {
    let node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

📏 Tree Height and Depth

What’s the Difference?

Imagine a building:

• Depth = Which floor are you on? (counting from the top, starting at 0)
• Height = How many floors are below you?

Depth of a Node

Depth = How many steps from the ROOT to reach this node

       1 (depth = 0)
      / \
     2   3 (depth = 1)
    /
   4 (depth = 2)

Height of a Node

Height = The longest path from this node DOWN to a leaf

function height(node) {
  if (node === null) return -1;

  let leftHeight = height(node.left);
  let rightHeight = height(node.right);

  return Math.max(leftHeight, rightHeight) + 1;
}

Tree Height = Height of the root node

graph TD
    A["1<br/>Height: 2"] --> B["2<br/>Height: 1"]
    A --> C["3<br/>Height: 0"]
    B --> D["4<br/>Height: 0"]

Quick Memory Trick:

• Depth = Looking DOWN from the roof (how far down am I?)
• Height = Looking UP from the ground (how tall is this subtree?)

📐 Tree Diameter

What is Diameter?

Diameter = The LONGEST path between ANY two nodes in the tree.

Think of it like this: If you stretched a string from one end of the tree to the other, what’s the longest string you could use?

       1
      / \
     2   3
    / \
   4   5

Diameter = 4 → 2 → 1 → 3 = 3 edges

The Clever Insight

The longest path might:

1. Go through the root, OR
2. Be entirely in the left subtree, OR
3. Be entirely in the right subtree

So at each node, we check: left height + right height + 2

function diameterOfBinaryTree(root) {
  let diameter = 0;

  function height(node) {
    if (node === null) return -1;

    let left = height(node.left);
    let right = height(node.right);

    // Update diameter at each node
    diameter = Math.max(diameter, left + right + 2);

    return Math.max(left, right) + 1;
  }

  height(root);
  return diameter;
}

🏆 Binary Tree Maximum Path Sum

The Challenge

Find the path with the BIGGEST sum of node values. The path can start and end at ANY node!

Think of nodes as piggy banks with coins. Find the path that collects the most coins!

       -10
       /  \
      9    20
          /  \
         15   7

Best path: 15 → 20 → 7 = 42

The Strategy

At each node, we have choices:

1. Take this node alone
2. Take this node + left path
3. Take this node + right path
4. Take left + this node + right (becomes a “bridge”)

function maxPathSum(root) {
  let maxSum = -Infinity;

  function findMax(node) {
    if (node === null) return 0;

    // Get max from children (ignore negatives)
    let leftMax = Math.max(0, findMax(node.left));
    let rightMax = Math.max(0, findMax(node.right));

    // Check if current path is the best
    let currentPath = leftMax + node.val + rightMax;
    maxSum = Math.max(maxSum, currentPath);

    // Return the best "arm" we can offer
    return node.val + Math.max(leftMax, rightMax);
  }

  findMax(root);
  return maxSum;
}

Key Insight: We can only “turn around” once! So we track the best complete path vs. the best arm to offer upward.

👨‍👩‍👧 Lowest Common Ancestor (LCA)

What is LCA?

The Lowest Common Ancestor is the closest shared ancestor of two people in the family tree.

Think about it: If you and your cousin want to find your closest shared grandparent, that’s the LCA!

         3
        / \
       5   1
      / \ / \
     6  2 0  8
       / \
      7   4

LCA of 5 and 1 = 3 (the root is their common ancestor) LCA of 5 and 4 = 5 (5 is an ancestor of 4!)

The Solution

function lowestCommonAncestor(root, p, q) {
  if (root === null) return null;

  // If we found one of the targets
  if (root === p || root === q) return root;

  // Search in left and right subtrees
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);

  // If both found something, root is LCA
  if (left && right) return root;

  // Otherwise, return whichever found something
  return left ? left : right;
}

How it works:

1. If current node is p or q, report it!
2. Ask left and right subtrees to find p and q
3. If both sides found something → current node is LCA
4. If only one side found → pass that result up

➕ Path Sum Problems

Problem 1: Does a Path Exist?

Question: Is there a root-to-leaf path that adds up to a target sum?

       5
      / \
     4   8
    /   / \
   11  13  4
  /  \      \
 7    2      1

Target = 22: Path 5 → 4 → 11 → 2 = 22 ✓

function hasPathSum(root, targetSum) {
  if (root === null) return false;

  // If we're at a leaf, check if sum matches
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }

  // Check left and right with remaining sum
  let remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) ||
         hasPathSum(root.right, remaining);
}

Problem 2: Find All Paths

Question: Find ALL root-to-leaf paths that sum to target.

function pathSum(root, targetSum) {
  let result = [];

  function findPaths(node, remaining, path) {
    if (node === null) return;

    path.push(node.val);

    // Check if leaf with correct sum
    if (!node.left && !node.right &&
        remaining === node.val) {
      result.push([...path]);
    }

    // Continue searching
    findPaths(node.left, remaining - node.val, path);
    findPaths(node.right, remaining - node.val, path);

    path.pop(); // Backtrack!
  }

  findPaths(root, targetSum, []);
  return result;
}

Problem 3: Count Paths with Sum (Any Start)

Question: How many paths (starting anywhere) add up to target?

function pathSumIII(root, targetSum) {
  let count = 0;
  let prefixSums = new Map([[0, 1]]);

  function dfs(node, currentSum) {
    if (node === null) return;

    currentSum += node.val;

    // Check if any prefix gives target
    count += prefixSums.get(currentSum - targetSum) || 0;

    // Add current sum to prefix map
    prefixSums.set(currentSum,
      (prefixSums.get(currentSum) || 0) + 1);

    dfs(node.left, currentSum);
    dfs(node.right, currentSum);

    // Backtrack
    prefixSums.set(currentSum,
      prefixSums.get(currentSum) - 1);
  }

  dfs(root, 0);
  return count;
}

🎯 Summary: Your Tree Toolkit

Remember: Trees are just organized families. Once you see them that way, every problem becomes a family reunion! 🌳✨