Leetcode 94. Binary Tree Inorder Traversal

Inorder Traversal of a Binary Tree in C++

Introduction

In this blog post, we will discuss the implementation of an algorithm to perform an inorder traversal on a binary tree. The goal is to return the inorder traversal of its nodes' values. We will provide a step-by-step explanation of the code and discuss its complexity analysis. Additionally, we will explore the Morris Traversal method, which utilizes a threaded binary tree to optimize the traversal process. Let's dive into the details!

Problem Statement

Given the root of a binary tree, we need to return the inorder traversal of its nodes' values. The inorder traversal visits the left subtree, then the current node, and finally the right subtree.

Solution Overview

To perform an inorder traversal iteratively, we can use a modified version of Morris Traversal. The algorithm avoids using an explicit stack and instead modifies the tree structure itself to achieve the desired traversal order. The main idea is to establish a temporary link between the rightmost node of the left subtree and the current node. This link allows us to traverse the tree in a predefined order without losing the original right subtree.

Solution Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        TreeNode* curr = root;
        TreeNode* pre;
        while (curr != nullptr) {
            if (curr->left == nullptr) {
                res.push_back(curr->val);
                curr = curr->right; // move to the next right node
            } else { // has a left subtree
                pre = curr->left;
                while (pre->right != nullptr) { // find the rightmost node in the left subtree
                    pre = pre->right;
                }
                pre->right = curr; // establish the temporary link
                TreeNode* temp = curr; // store the current node
                curr = curr->left; // move to the top of the new tree
                temp->left = nullptr; // set the original left node to nullptr to avoid infinite loops
            }
        }
        return res;
    }
};
  

The function inorderTraversal takes the root of the binary tree as input and returns a vector res containing the inorder traversal of the tree. We start with an empty result vector and initialize two pointers, curr and pre, to the root of the tree.

The algorithm uses a while loop to traverse the tree. Inside the loop, we check if the current node curr has a left subtree. If it doesn't, we push the value of curr to the result vector res and move curr to its right child using curr = curr->right. This step ensures that we traverse the right subtree after visiting the current node and its left subtree.

If curr has a left subtree, we need to establish a temporary link to the rightmost node of the left subtree. This link will allow us to return to the current node later. We initialize pre to the rightmost node of the left subtree by repeatedly moving pre to its right child until we reach the rightmost node.

After finding the rightmost node, we set pre->right = curr to establish the temporary link. We also store the current node in temp before moving curr to its left child. Setting temp->left = nullptr avoids infinite loops by disconnecting the original left subtree.

Finally, we return the result vector res containing the inorder traversal of the binary tree.

Approach 3: Morris Traversal

In this method, we have to use a new data structure - Threaded Binary Tree, and the strategy is as follows:

1. Initialize the current node as the root.
2. While the current node is not NULL:
   • If the current node does not have a left child, add its value to the result vector and move to the right child (curr = curr->right).
   • If the current node has a left child:
     • Find the rightmost node in the left subtree (the node with no right child). We will call this node pre.
     • If pre->right is NULL, set pre->right = curr to establish the temporary link from pre to curr. This link indicates that we have visited the left subtree of curr.
     • Move to the left child (curr = curr->left).
     • If pre->right is not NULL, it means we have already visited the left subtree of curr. Remove the temporary link by setting pre->right = NULL and add the value of curr to the result vector.

The Morris Traversal method allows us to perform an inorder traversal without using an explicit stack. By utilizing the threaded binary tree concept, we establish temporary links that guide the traversal process.

Complexity Analysis

The time complexity of the Morris Traversal algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and establishing the temporary links takes constant time for each node.

The space complexity is O(1) since we do not require any additional data structures besides the output vector.

Conclusion

In this blog post, we explored an iterative solution to perform an inorder traversal on a binary tree. The algorithm utilizes the Morris Traversal method, which modifies the tree structure itself to achieve the desired traversal order. We provided a step-by-step explanation of the code, discussed the complexity analysis, and introduced the threaded binary tree concept. The Morris Traversal method offers an efficient approach for inorder tree traversal without the need for an explicit stack.