Binary Tree in Action (Traversal)

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

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:

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

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);
    }
}

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

    // binary tree traversal function
    void traverse(TreeNode* root) {
        if(root != NULL) {
            // *** pre-order position ***
            // what each node needs to do is to swap its left and right child nodes
            TreeNode* tmp = root->left;
            root->left = root->right;
            root->right = tmp;

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

class Solution:
    # main function
    def invertTree(self, root):
        # traverse the binary tree, swap the children of each node
        self.traverse(root)
        return root

    # binary tree traversal function
    def traverse(self, root):
        if not root:
            return 
        
        # *** pre-order position ***
        # what each node needs to do is swap its left and right children
        tmp = root.left
        root.left = root.right
        root.right = tmp

        # traversal framework, go traverse the nodes of the left and right subtrees
        self.traverse(root.left)
        self.traverse(root.right)

// main function
func invertTree(root *TreeNode) *TreeNode {
    // traverse the binary tree, swap the child nodes of each node
    traverse(root)
    return root
}

// binary tree traversal function
func traverse(root *TreeNode) {
    if root == nil {
        return
    }

    // *** preorder position ***
    // what each node needs to do is swap its left and right children
    tmp := root.Left
    root.Left = root.Right
    root.Right = tmp

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

// main function
var invertTree = function(root) {
    traverse(root);
    return root;
};

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

    // *** preorder position ***
    // what each node needs to do is swap its left and right children
    let tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // traversal framework, go and 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);

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

# Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
def invertTree(self, root: TreeNode) -> TreeNode:

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

// Definition: Invert the binary tree rooted at
// 'root', return the root node of the inverted tree
var invertTree = function(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;
    }
}

class Solution {
public:
    // Definition: Invert the binary tree rooted at
    // 'root', return the root node of the inverted tree
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        // Utilize the function definition to invert the 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;
    }
};

class Solution:
    # Definition: Invert the binary tree rooted at
    # 'root', return the root node of the inverted tree
    def invertTree(self, root):
        if root is None:
            return None
        # Utilize the function definition to invert left and right subtrees first
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # Then swap the left and right child nodes
        root.left, root.right = right, left

        # Consistent with the definition logic: the tree
        # rooted at 'root' has been inverted, return root
        return root

// Definition: Invert the binary tree rooted at
// 'root', return the root node of the inverted tree
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // Use the function definition to invert the left and right subtrees first
    left := invertTree(root.Left)
    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
}

// Definition: Invert the binary tree rooted at
// 'root', and return the root node of the inverted tree
var invertTree = function(root) {
    if (root == null) {
        return null;
    }
    // Utilize the function definition to invert left and right subtrees first
    var left = invertTree(root.left);
    var 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:

116. Populating Next Right Pointers in Each Node | LeetCode |  🟠

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, 212 - 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.

The problem is from LeetCode 116. Populating Next Right Pointers in Each Node.

// Function signature
Node connect(Node root);

// Function signature
Node* connect(Node* root);

# Function signature
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':

// Function signature
func connect(root *Node) *Node

// Function signature
var connect = function(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);
}

// Binary tree traversal function
void traverse(TreeNode* 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);
}

# Binary tree traversal function
def traverse(root):
    if root is None or root.left is None:
        return
    # Point the next pointer of the left child to the right child
    root.left.next = root.right

    traverse(root.left)
    traverse(root.right)

// Binary tree traversal function
func traverse(root *Node) {
    if root == nil || root.Left == nil {
        return
    }
    // Point the Next pointer of the left child to the right child
    root.Left.Next = root.Right

    traverse(root.Left)
    traverse(root.Right)
}

// Binary tree traversal function
var traverse = function(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);
    }
}

class Solution {
public:
    // Main function
    Node* connect(Node* root) {
        if (root == nullptr) return nullptr;
        // 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 == nullptr || node2 == nullptr) {
            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 different parents
        traverse(node1->right, node2->left);
    }
};

class Solution:
    # Main function
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        # Traverse the "ternary tree" and connect adjacent nodes
        self.traverse(root.left, root.right)
        return root

    # Ternary tree traversal frameworkf'd
    def traverse(self, node1: 'Node', node2: 'Node') -> None:
        if not node1 or not node2:
            return
        # Pre-order position
        # Connect the two input nodes
        node1.next = node2 
        
        # Connect two child nodes with the same parent
        self.traverse(node1.left, node1.right)
        self.traverse(node2.left, node2.right)
        # Connect two child nodes across different parents
        self.traverse(node1.right, node2.left)

// Main function
func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    // Traverse the "ternary tree" and connect adjacent nodes
    traverse(root.Left, root.Right)
    return root
}

// Ternary tree traversal framework
func traverse(node1 *Node, node2 *Node) {
    if node1 == nil || node2 == nil {
        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 different parents
    traverse(node1.Right, node2.Left)
}

var connect = function(root) {
    // main function
    if (root == null) return null;
    // traverse the "ternary tree" and connect adjacent nodes
    traverse(root.left, root.right);
    return root;

    // ternary tree traversal framework
    function traverse(node1, node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        // *** pre-order position ***
        // connect the two input nodes
        node1.next = node2;
        
        // connect two child nodes of the same parent
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // connect two child nodes across different parents
        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:

114. Flatten Binary Tree to Linked List | LeetCode |  🟠

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 problem is from LeetCode 114. Flatten Binary Tree to Linked List.

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

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

# The function signature is as follows
def flatten(self, root: Optional[TreeNode]) -> None:

// The function signature is as follows
func flatten(root *TreeNode)

// The function signature is as follows
var flatten = function(root) {};

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

At first glance, it seems possible: do a preorder traversal of the whole tree, and build a "linked list" as you go:

// 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);
}

// 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 == nullptr) {
        return;
    }
    // Pre-order position
    p->right = new TreeNode(root->val);
    p = p->right;

    traverse(root->left);
    traverse(root->right);
}

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

def traverse(root: TreeNode):
    if root is None:
        return
    # Pre-order position
    p.right = TreeNode(root.val)
    p = p.right

    traverse(root.left)
    traverse(root.right)

var p *TreeNode

// Virtual head node, dummy.right is the result
var dummy = newTreeNode(-1)
p = dummy

func traverse(root *TreeNode) {
	if root == nil {
		return
	}
	// Pre-order position
	p.Right = &TreeNode{Val: root.Val}
	p = p.Right

	traverse(root.Left)
	traverse(root.Right)
}

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

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

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

But pay attention to the flatten function's signature. Its return type is void, which means the problem wants us to flatten the tree in place.

So, we cannot simply solve this by just traversing the tree.

2. Can we solve this problem using the "divide and conquer" 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);

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

# Definition: Input node root, then the binary tree
# rooted at root will be flattened into a linked list
def flatten(self, root: Optional[TreeNode]) -> None:

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

// Definition: Input node root, then the binary tree
// rooted at root will be flattened into a linked list
var flatten = function(root) {};

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

For a node x, we can do the following steps:

1. Use flatten(x.left) and flatten(x.right) to flatten the left and right subtrees of x.

2. Attach x's right subtree to the end of the left subtree, then move the entire left subtree to the right.

In this way, the whole binary tree with root x is flattened, which matches the definition of flatten(x).

Here's the code:

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;
    }
}

class Solution {
public:
    // Definition: flatten the tree rooted at 'root' into a linked list
    void flatten(TreeNode* root) {
        // base case
        if (root == nullptr) return;

        // Use 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 = nullptr;
        root->right = left;

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

class Solution:
    # Definition: flatten the tree rooted at 'root' into a linked list
    def flatten(self, root) -> None:
        # base case
        if root is None:
            return

        # Use the definition to flatten left and right subtrees
        self.flatten(root.left)
        self.flatten(root.right)

        # Post-order traversal position
        # 1. Left and right subtrees have been flattened into linked lists
        left = root.left
        right = root.right

        # 2. Make the left subtree the new right subtree
        root.left = None
        root.right = left

        # 3. Attach the original right subtree to the end of the current right subtree
        p = root
        while p.right is not None:
            p = p.right
        p.right = right

// Definition: flatten the tree with root as the root into a linked list
func flatten(root *TreeNode) {
    // base case
    if root == nil {
        return
    }
    
    // Using the definition, 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 a linked list
    left := root.Left
    right := root.Right
       
    // 2. Make the left subtree the right subtree
    root.Left = nil
    root.Right = left

    // 3. Attach the original right subtree to the end of the current right subtree
    p := root
    for p.Right != nil {
        p = p.Right
    }
    p.Right = right
}

var flatten = function(root) {
    // Definition: flatten the tree with root as the root into a linked list
    // 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 a linked list
    var left = root.left;
    var right = root.right;

    // 2. Make the left subtree the right subtree
    root.left = null;
    root.right = left;

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

This is the beauty of recursion. How does flatten flatten the left and right subtrees? It's hard to explain in detail, but as long as you know the definition of flatten and use it, let every node do its part, the flatten function will work as defined.

With this, the problem is solved. The recursive thinking in our earlier article Reverse Nodes in k-Group is also similar to this problem.

Finally, let's review the main ideas for solving binary tree problems.

There are two main approaches to binary tree problems:

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

2. Can you define a recursive function, and use the answers from subproblems (subtrees) to get the answer to the main problem? If yes, write out this recursive function and use its return value. This is called the "divide and conquer" approach.

No matter which approach you use, always think:

If you focus on a single tree node, what does it need to do? When does it need to do it (preorder, inorder, or postorder)? You don't need to worry about other nodes; the recursive function will handle them the same way.

I hope you can understand this and use it for all binary tree problems.

That's all for this article. For more classic binary tree exercises and practice on recursion, see the Binary Tree Recursion Exercises section.