Tree Data Structure

From linear patterns to branching structure

Now that we've covered Introduction to Data Structures, Recursion, and Sliding Windows, you're ready for a structure that shows up everywhere: trees.

Arrays and sliding windows are naturally linear: move left to right, maintain a range, update an invariant.

Trees are different:

• Data branches into parent-child relationships
• Recursion becomes a natural navigation tool
• Many interview problems become questions about shape, subtrees, and ordering rules

As a Java developer, you've already used tree-like ideas indirectly: file systems, DOM nodes, JSON objects, dependency graphs, indexes, and expression parsing.

In this lesson, we'll focus on the tree data structure itself: what it is, how to model it, and how to reason about its most common patterns.

A tree is hierarchical

A tree is a collection of nodes connected by edges where each node can have children.

Unlike arrays, trees do not have one obvious next element. A node may branch into multiple possible paths.

        A        <- root
      /   \
     B     C     <- children of A
    / \     \
   D   E     F   <- leaves: D, E, F

Key terms:

• Root: the top node, with no parent
• Parent: a node directly above another node
• Child: a node directly below another node
• Leaf: a node with no children
• Subtree: any node plus all of its descendants
• Depth: distance from root to a node
• Height: longest distance from a node down to a leaf

The most important mental shift: with trees, you often solve the problem for one node, then trust recursion to solve the same problem for its subtrees.

Which statement best describes a basic tree structure?

A node is data plus links

In Java, a tree node is usually modeled as an object containing:

• A value
• References to child nodes

For a binary tree, each node has at most two children: left and right.

The structure is not stored by index like an array. It is stored by references between objects.

This small example builds a tree manually and prints a few relationships.

```java
public class Main {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);

        System.out.println("Root: " + root.value);
        System.out.println("Left child: " + root.left.value);
        System.out.println("Right child: " + root.right.value);
        System.out.println("Is 7 a leaf? " + (root.left.right.left == null && root.left.right.right == null));
    }
}
```

Traversal means visiting nodes

Because trees branch, you need a strategy for visiting nodes.

The classic depth-first traversal orders are:

• Preorder: node, left, right
• Inorder: left, node, right
• Postorder: left, right, node

This is where the Recursion lesson becomes immediately useful. Each traversal says:

1. What should I do at the current node?
2. When should I visit the left subtree?
3. When should I visit the right subtree?

The code below prints all three orders for the same tree.

```java
public class Main {
    static class TreeNode {
        int value;
        TreeNode left, right;
        TreeNode(int value) { this.value = value; }
    }

    static void preorder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.value + " ");
        preorder(node.left);
        preorder(node.right);
    }

    static void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value + " ");
        inorder(node.right);
    }

    static void postorder(TreeNode node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value + " ");
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);

        System.out.print("Preorder: ");
        preorder(root);
        System.out.println();

        System.out.print("Inorder: ");
        inorder(root);
        System.out.println();

        System.out.print("Postorder: ");
        postorder(root);
        System.out.println();
    }
}
```

True or false: In a binary tree, each node may have at most two children.

Binary Search Tree invariant

A Binary Search Tree, or BST, is a binary tree with an ordering rule:

For every node:
left subtree values  <  node value  <  right subtree values

Example:

        10
      /    \
     5      15
    / \       \
   3   7       20

This rule gives the tree a useful search pattern:

• If the target equals the current node, found it
• If the target is smaller, go left
• If the target is larger, go right

Notice how this connects back to Introduction to Data Structures: the interface might be "search for value," but the implementation shape controls the cost.

In a Binary Search Tree, values less than a node belong in that node's ____ subtree.

Tree performance depends on shape

A BST can be very efficient, but only if its height stays small.

Balanced-ish tree:

        8
      /   \
     4     12
    / \   /  \
   2   6 10  14

Skewed tree:

1
 \
  2
   \
    3
     \
      4

In a balanced BST, search can be about O(log n) because each step discards a large part of the tree.

In a skewed BST, search degrades to O(n) because the tree behaves like a linked list.

This example compares the number of recursive checks needed for two different shapes.

```java
public class Main {
    static class TreeNode {
        int value;
        TreeNode left, right;
        TreeNode(int value) { this.value = value; }
    }

    static int searchSteps(TreeNode node, int target) {
        int steps = 0;
        while (node != null) {
            steps++;
            if (target == node.value) return steps;
            node = target < node.value ? node.left : node.right;
        }
        return steps;
    }

    public static void main(String[] args) {
        TreeNode balanced = new TreeNode(8);
        balanced.left = new TreeNode(4);
        balanced.right = new TreeNode(12);
        balanced.left.left = new TreeNode(2);
        balanced.left.right = new TreeNode(6);
        balanced.right.left = new TreeNode(10);
        balanced.right.right = new TreeNode(14);

        TreeNode skewed = new TreeNode(1);
        skewed.right = new TreeNode(2);
        skewed.right.right = new TreeNode(3);
        skewed.right.right.right = new TreeNode(4);

        System.out.println("Steps to find 14 in balanced tree: " + searchSteps(balanced, 14));
        System.out.println("Steps to find 4 in skewed tree: " + searchSteps(skewed, 4));
    }
}
```

How to recognize tree problems

When you see a tree problem, pause before coding and ask:

1. What kind of tree is it?

   • General tree?
   • Binary tree?
   • Binary Search Tree?

2. What does one node need to know?

   • Its value?
   • Its children?
   • Information returned from subtrees?

3. Which traversal fits the goal?

   • Need to process parent before children? Preorder.
   • Need sorted order in a BST? Inorder.
   • Need child results before parent? Postorder.

4. What is the shape cost?

   • Balanced: often shallow
   • Skewed: potentially linear

The biggest lesson: trees combine the data-shape thinking from Introduction to Data Structures with the call-stack thinking from Recursion.

Next, we'll move into Dynamic Programming, where solving overlapping subproblems becomes the main pattern.