Tree Algorithms

Trees are interview accelerators

Now that we've covered Dynamic Programming and Graph Algorithms, we're ready for a structure that quietly combines both worlds: trees.

A tree is a graph with constraints:

• connected
• acyclic
• usually rooted in interview problems
• every subtree looks like a smaller version of the original problem

That last point is the big one. Tree questions often become clean recursive contracts: “What information should a child return to its parent?”

In FAANG-style interviews, tree problems test whether you can:

• choose the right traversal
• define what each recursive call returns
• preserve invariants like BST ordering
• combine local and child information without double-counting

We’ll build on the representation-first habit from the introduction and the DFS/BFS state thinking from Graph Algorithms — but specialize it for trees.

Don’t say “DFS” too early

In the Graph Algorithms lesson, DFS was about reachability and state. In trees, DFS is usually about timing.

For a node x, ask:

• Preorder: Do I need to act before children?
• Inorder: Is this a binary search tree ordering problem?
• Postorder: Do I need children’s answers before computing mine?

Example tree:

      1
     / \
    2   3
   / \
  4   5

Outputs:

• preorder: 1 2 4 5 3
• inorder: 4 2 5 1 3
• postorder: 4 5 2 3 1

The traversal is not decoration. It is the shape of your reasoning.

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void preorder(Node* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "preorder: ";
    preorder(root);
    cout << "\n";

    cout << "inorder: ";
    inorder(root);
    cout << "\n";

    cout << "postorder: ";
    postorder(root);
    cout << "\n";

    return 0;
}
```

The core tree interview question

Most nontrivial tree problems become easier when you define a return contract:

“For any node, what exact information does this function return about the subtree rooted here?”

Good contracts are local, reusable, and composable.

Examples:

Problem type Useful return contract height height of this subtree balanced tree height, or failure marker diameter longest downward path plus global best max path sum best path extending upward subtree contains target boolean or pointer serialize tree encoded representation

A common mistake is trying to solve the whole tree at every node. Instead, solve the subtree and return just enough information upward.

This mirrors the State Is Contract idea from Dynamic Programming, but here the dependency graph is already shaped like a tree.

A binary tree problem asks:

“For each node, compute whether its left and right subtrees are valid before deciding whether the current subtree is valid.”

Which traversal style best matches this dependency?

Root-to-leaf path sum

Classic prompt:

Given a binary tree and target sum, determine if any root-to-leaf path sums to the target.

The contract:

hasPathSum(node, remaining) returns whether some path from node down to a leaf totals remaining.

Key details interviewers watch for:

• A valid path must end at a leaf.
• Subtract the current node value before moving down.
• The empty child is not a successful path by itself.

This is a simple example, but it trains the habit needed for harder tree DP problems: carry only the information that changes along the path.

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool hasPathSum(Node* root, int target) {
    if (!root) return false;

    int remaining = target - root->val;

    if (!root->left && !root->right) {
        return remaining == 0;
    }

    return hasPathSum(root->left, remaining) ||
           hasPathSum(root->right, remaining);
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(4);
    root->right = new Node(8);
    root->left->left = new Node(11);
    root->left->left->left = new Node(7);
    root->left->left->right = new Node(2);
    root->right->left = new Node(13);
    root->right->right = new Node(4);

    int target = 22;
    cout << boolalpha;
    cout << "Has root-to-leaf path sum " << target << "? "
         << hasPathSum(root, target) << "\n";

    return 0;
}
```

True or false:

Because a tree has no cycles, recursive DFS on a rooted binary tree usually does not need a visited set.

BSTs are not just local comparisons

A common trap:

      10
     /  \
    5    15
        /  \
       6    20

Checking only left < node < right at each node would accept this tree, but it is invalid: 6 is in the right subtree of 10, so it must be greater than 10.

Correct contract:

Every node must fall within an allowed range inherited from its ancestors.

So validation carries bounds downward:

• left child range: (low, node->val)
• right child range: (node->val, high)

This is representation-first thinking again: the node’s position in the tree gives it constraints.

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node* left;
    Node* right;
    Node(long long v) : val(v), left(nullptr), right(nullptr) {}
};

bool isValidBST(Node* root, long long low, long long high) {
    if (!root) return true;

    if (root->val <= low || root->val >= high) {
        return false;
    }

    return isValidBST(root->left, low, root->val) &&
           isValidBST(root->right, root->val, high);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->right->left = new Node(6);
    root->right->right = new Node(20);

    cout << boolalpha;
    cout << "Is valid BST? "
         << isValidBST(root, LLONG_MIN, LLONG_MAX) << "\n";

    return 0;
}
```

When a tree problem requires each node to compute its answer after receiving results from its children, the DFS order is ____.

One return, one global answer

Tree diameter asks for the longest path between any two nodes. The path may or may not pass through the root.

At each node, two ideas coexist:

1. What can this node return upward?
2. What complete answer can be formed here?

Return contract:

height(node) returns the longest downward path from this node to a leaf.

Local candidate diameter:

left height + right height

The recursive call returns height upward, while a separate best value records the largest full path seen anywhere.

This pattern appears in many harder tree problems: return the value useful to the parent, but update the global or referenced answer with a complete candidate.

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int heightAndUpdateDiameter(Node* root, int& best) {
    if (!root) return 0;

    int leftHeight = heightAndUpdateDiameter(root->left, best);
    int rightHeight = heightAndUpdateDiameter(root->right, best);

    best = max(best, leftHeight + rightHeight);

    return 1 + max(leftHeight, rightHeight);
}

int diameter(Node* root) {
    int best = 0;
    heightAndUpdateDiameter(root, best);
    return best;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Diameter in edges: " << diameter(root) << "\n";
    return 0;
}
```

Your tree problem checklist

When a tree problem appears, run this loop:

1. Identify representation

   • Binary tree nodes?
   • BST?
   • N-ary tree?
   • Parent pointers?
   • Adjacency list?

2. Choose traversal by dependency

   • top-down constraints or path state → preorder-style
   • sorted BST output → inorder
   • subtree aggregation → postorder
   • shortest number of edges or levels → BFS

3. Define the contract

   • What does each call receive?
   • What does each call return?
   • Is there a separate global/reference answer?

4. Handle boundaries deliberately

   • null node
   • leaf node
   • duplicate values
   • integer limits
   • skewed tree recursion depth

5. State complexity in tree terms

   • Usually O(n) time because each node is visited once.
   • Space is usually O(h) recursion stack, where h is tree height.

Next, we’ll zoom out into broader Problem Solving Techniques so you can recognize when a tree problem is actually asking for a known pattern in disguise.