binary-tree-practice1

::: info Prerequisites

Before reading this article, you should first study:

• Basics of Binary Tree Structure

• Binary Tree DFS/BFS Traversal

• Binary Tree Essentials (Guiding Principles)

:::

This article continues from Binary Tree Essentials (Guiding Principles). Let’s first review the key points summarized in the previous article:

::: note Note

There are two main thinking patterns for solving binary tree problems:

1. Can you get the answer by traversing the binary tree once? If yes, use a traverse function with external variables—this is called the "traversal" approach.

2. Can you define a recursive function that derives the answer to the original problem using answers from its subproblems (subtrees)? If yes, write out this recursive function and make full use of its return value—this is called the "problem decomposition" approach.

No matter which approach you use, you should always think:

If you isolate a single tree node, what does it need to do? At what point (preorder/inorder/postorder) should it do it? You don’t need to worry about other nodes, as the recursive function will perform the same operation on all of them.

:::

This article uses a few simple examples to help you practice these key principles, and to understand the differences and connections between the "traversal" and "problem decomposition" approaches.

Problem 1: Invert Binary Tree

Let's start with an easy problem. Look at LeetCode 226: Invert Binary Tree. The input is the root node root of a binary tree. You need to flip the tree so that it becomes its mirror image. For example, the input tree is:

root:
  value: 4
  left:
    value: 2
    left:
      value: 1
    right:
      value: 3
  right:
    value: 7
    left:
      value: 6
    right:
      value: 9

After the algorithm inverts the tree, it should look like this:

root:
  value: 4
  left:
    value: 7
    left:
      value: 9
    right:
      value: 6
  right:
    value: 2
    left:
      value: 3
    right:
      value: 1

It is easy to see that if you swap the left and right children of every node in the tree, the whole tree will be inverted.

Now, let's recall our general approach for binary tree problems:

1. Can we solve this problem with a traversal approach?

Yes. We can write a traverse function to visit every node, and at each node, swap its left and right children.

What should we do at each node? Just swap its left and right children.

When should we do this? We can do it in pre-order, in-order, or post-order. Any of them work.

So, the code can be written like this:

class Solution {
    // main function
    public TreeNode invertTree(TreeNode root) {
        // traverse the binary tree, swap the child nodes of each node
        traverse(root);
        return root;
    }

    // binary tree traversal function
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        // *** pre-order position ***
        // what each node needs to do is to swap its left and right children
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        // traversal framework, go traverse the nodes of the left and right subtrees
        traverse(root.left);
        traverse(root.right);
    }
}

You can move the swap code from pre-order to post-order and it will still work. But moving it to in-order requires some changes. This should be easy to see, so I won't explain more.

So, we have solved the problem using traversal. But let's also think about another way.

2. Can we solve this problem with a divide-and-conquer approach?

Let's define what the invertTree function does:

// Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
TreeNode invertTree(TreeNode root);

Now, for a given node x, what can we do with invertTree(x)?

We can call invertTree(x.left) to invert the left subtree, and invertTree(x.right) to invert the right subtree. Then, we swap the left and right children of x. This completes the inversion of the subtree rooted at x.

Here is the code:

class Solution {
    // Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // Utilize the function definition to invert left and right subtrees first
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // Then swap the left and right child nodes
        root.left = right;
        root.right = left;

        // Consistent with the definition logic: the binary tree rooted at 'root' has been inverted, return root
        return root;
    }
}

In this divide-and-conquer way, the key is to give the recursive function a clear definition, and then write the code based on this definition. If your logic is self-consistent, your algorithm should be correct.

That's all for this problem. Both traversal and divide-and-conquer work. Let's look at the next problem.

Problem 2: Populating Next Right Pointers in Each Node

This is LeetCode problem 116: Populating Next Right Pointers in Each Node. Let's look at the problem:

LeetCode 116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:**

**Input:** root = [1,2,3,4,5,6,7]
**Output:** [1,#,2,3,#,4,5,6,7,#]
**Explanation: **Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:**

**Input:** root = []
**Output:** []

Constraints:

• The number of nodes in the tree is in the range [0, 2^(12) - 1].

• -1000 <= Node.val <= 1000

Follow-up:

• You may only use constant extra space.

• The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

// Function signature
Node connect(Node root);

The goal is to connect all nodes at the same level in a binary tree using the next pointer:

The problem also says the input is a "perfect binary tree," which means the tree is shaped like an equilateral triangle. Except for the rightmost node at each level, every node has a neighbor to its right, and the next pointer should point to that neighbor. The rightmost node's next pointer should point to null.

How do we solve this problem? Let's recall the general ideas for solving binary tree problems:

1. Can we solve this problem using a "traversal" approach?

Of course, we can.

Each node just needs to set its next pointer to the node on its right.

You might want to write code similar to the previous problem, like this:

// Binary tree traversal function
void traverse(Node root) {
    if (root == null || root.left == null) {
        return;
    }
    // Point the next pointer of the left child to the right child
    root.left.next = root.right;

    traverse(root.left);
    traverse(root.right);
}

But this code has a big problem. It only connects two nodes with the same parent. Look at this picture again:

Node 5 and node 6 don't have the same parent. According to this code, they won't be connected, which is not what we want. So where is the problem?

The traditional traverse function visits every node in the binary tree, but now we want to visit the "gap" between two neighboring nodes.

So, let's try to see the tree differently. Think of each box in the picture as a node:

Now, the binary tree becomes like a ternary tree. Each node in the ternary tree represents two neighboring nodes from the binary tree.

We just need to write a traverse function for this ternary tree. Each "ternary tree node" connects its two binary tree nodes:

class Solution {
    // Main function
    public Node connect(Node root) {
        if (root == null) return null;
        // Traverse the "ternary tree" and connect adjacent nodes
        traverse(root.left, root.right);
        return root;
    }

    // Ternary tree traversal framework
    void traverse(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        // *** Pre-order position ***
        // Connect the two input nodes
        node1.next = node2;
        
        // Connect two child nodes with the same parent
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // Connect two child nodes across parent nodes
        traverse(node1.right, node2.left);
    }
}

With this, the traverse function will visit all the "gaps" between neighboring binary tree nodes and connect them correctly. This solves the problem perfectly.

2. Can we solve this problem by "breaking it into subproblems"?

Hmm, there doesn't seem to be a good way to do this. So, we can't use the "decompose subproblems" idea for this problem.

Problem 3: Flatten Binary Tree to Linked List

This is LeetCode problem 114 "Flatten Binary Tree to Linked List". Let's look at the problem:

LeetCode 114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

• The "linked list" should be in the same order as a pre-order** traversal** of the binary tree.

Example 1:**

**Input:** root = [1,2,5,3,4,null,6]
**Output:** [1,null,2,null,3,null,4,null,5,null,6]

Example 2:**

**Input:** root = []
**Output:** []

Example 3:**

**Input:** root = [0]
**Output:** [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

// The function signature is as follows
void flatten(TreeNode root);

1. Can we solve this using the "traversal" approach?

At first glance, it seems possible: perform a preorder traversal of the entire tree, building a "linked list" as you traverse:

// Virtual head node, dummy.right is the result
TreeNode dummy = new TreeNode(-1);
// Pointer used to build the linked list
TreeNode p = dummy;

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // Pre-order position
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}

But notice the signature of the flatten function—its return type is void. This means the problem wants us to flatten the binary tree into a linked list in place.

This makes it impossible to solve the problem with simple binary tree traversal.

2. Can we solve this using the "decompose the problem" approach?

Let's try to define the flatten function:

// Definition: Input node root, then the binary tree rooted at root will be flattened into a linked list
void flatten(TreeNode root);

With this function definition, how do we flatten a tree into a linked list as required?

For a node x, you can follow this process:

1. First use flatten(x.left) and flatten(x.right) to flatten x's left and right subtrees.

2. Set the entire left subtree as the right subtree, then attach the original right subtree to the end of the current right subtree.

This way, the entire binary tree rooted at x is flattened, which is exactly what the flatten(x) definition requires.

Here's the code implementation:

class Solution {
    // Definition: flatten the tree with root as the root node into a linked list
    public void flatten(TreeNode root) {
        // base case
        if (root == null) return;
        
        // Utilize the definition to flatten the left and right subtrees
        flatten(root.left);
        flatten(root.right);

        // *** Post-order traversal position ***
        // 1. Left and right subtrees have been flattened into linked lists
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        // 2. Make the left subtree the new right subtree
        root.left = null;
        root.right = left;

        // 3. Attach the original right subtree to the end of the current right subtree
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

See, this is the magic of recursion. Can you explain exactly how the flatten function flattens the left and right subtrees?

It's not easy to articulate, but as long as you know the definition of flatten and use that definition to let each node do what it's supposed to do, the flatten function will work according to its definition.

With that, this problem is solved. The recursive approach in our previous article Reverse Nodes in k-Group shares some similarities with this problem.

Finally, let's revisit the binary tree problem-solving framework to bring things full circle.

There are two approaches for solving binary tree problems:

1. Can you get the answer by traversing the binary tree once? If yes, use a traverse function with external variables. This is the "traversal" approach.

2. Can you define a recursive function that derives the answer to the original problem from the answers of subproblems (subtrees)? If yes, write out the definition of this recursive function and fully utilize its return value. This is the "decompose the problem" approach.

Regardless of which approach you use, you need to think about:

If you isolate a single binary tree node, what does it need to do? When (pre/in/post-order position) does it need to do it? Don't worry about the other nodes—the recursive function will execute the same operation on all nodes.

I hope you can internalize this and apply it to all binary tree problems.

That's all for this article. For more classic binary tree exercises and recursion training, see Recursion Practice in the binary tree chapter.