94. Binary Tree Inorder Traversal

EasyStackTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem asks us to perform an inorder traversal on a binary tree and return the sequence of values from the nodes. In binary tree traversal, there are three types of depth-first searches - inorder, preorder, and postorder. Specifically, the inorder traversal follows a defined sequence to visit the nodes:

  • Visit the left subtree
  • Visit the root node
  • Visit the right subtree

This pattern is recursive and is applied to each subtree within the tree. The result of performing an inorder traversal is that the nodes of the tree are visited in ascending order if the binary tree is a binary search tree. For this problem, we are required to collect the values of the nodes in the order they are visited and return them as a list.

Intuition

The proposed solution uses the Morris Traversal approach, which is an optimized way to do tree traversal without recursion and without using extra space for a stack. The basic idea of Morris Traversal is to link the rightmost node of a node's left subtree back to the node itself, which helps us to get back to the root node after we are done traversing the left subtree.

Here's the process how we arrive at the Morris Traversal solution approach:

  • Start with the root node.
  • If the root has no left child, it means this node can be visited now, so we add its value to the result list and move to its right child.
  • If the root has a left child, find the rightmost node in the left subtree (the inorder predecessor of root).
    • If the rightmost node has no right child (is not already linked back to the root), we create a temporary link from it to the root and move the root to its left child.
    • If the rightmost node's right child is the root (already linked back), it means we have visited the left subtree already, so we add the root's value to the result list, unlink (restore the tree structure), and move to the right child of the root.

This approach allows us to use the tree structure itself as a way to navigate through the tree without additional memory usage for the call stack or an auxiliary stack, thus giving us the inorder sequence of node values in O(n) time with O(1) space complexity.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How does quick sort divide the problem into subproblems?

Solution Approach

The solution provided implements the Morris Traversal as the algorithm for inorder traversal of the binary tree. Here is a walkthrough of the implementation:

  • The function inorderTraversal begins with an empty list ans, which will contain the sequence of node values in inorder.

  • The main loop runs as long as there is a root to process. The steps in the loop correspond to the ideas discussed in the intuition:

    • If root.left is None, it implies there's no left subtree, and the root node can be visited. So, root.val is added to the ans list and root is updated to be root.right, moving on to the next node in the inorder sequence.

    • If root.left exists, this means we have a left subtree that needs to be processed first. We then find the inorder predecessor of the root by traversing rightwards (prev = prev.right) until we find a node that either has no right child or whose right child is the current root. This predecessor will act as a temporary bridge back to the root after we've finished with the left subtree.

      • If the predecessor's (prev) right child is None, this means we haven't processed the left subtree yet. We, therefore, make a temporary link from the predecessor's right child to the current root (prev.right = root). This allows us to come back to the root after we're done with the left subtree. Then we move root to its left child and continue the loop.

      • If the predecessor's right child is the current root, this indicates we've returned from traversing the left subtree, and it's now time to visit the root. We, therefore, add root.val to the ans list, remove the temporary link to restore the tree's structure (prev.right = None), and proceed with root.right.

The loop continues until every node has been visited in the inorder sequence. Since we're altering the tree during traversal, the Morris Traversal uses no additional space for data structures like stacks or the system call stack, making it a very space-efficient approach.

The result is a list of node values ans that have been collected in inorder. This list is then returned, providing the solution to the problem.

This method achieves an O(n) time complexity for traversing through n nodes and O(1) space complexity, as it does not utilize recursion or an explicit stack to maintain the state during the traversal.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's consider a simple binary tree for our example:

1    2
2   / \
3  1   3

In this tree, we have three nodes, where 2 is the root node, 1 is to its left, and 3 is to its right. We want to perform an inorder traversal, which would visit the nodes in the order 1, 2, 3, as 1 comes first in the left subtree, followed by 2, the root, and finally 3 in the right subtree.

Using the Morris Traversal approach, we would proceed as follows:

  1. We start at the root, which is 2. The root has a left child, so we find the inorder predecessor which is the rightmost node in the left subtree of 2 (which happens to be the node itself since it has no right child in its subtree). Since node 1 has no right child, we make a temporary link from node 1 to node 2 and then move the root to its left child (1).

  2. Now the current root is 1, which has no left child. Since there's no left subtree to process, we add 1 to the ans list. There is also no right child, so we would follow the temporary link back to 2. After visiting node 1, we have ans = [1].

  3. We arrive back at 2 because of the temporary link. We remove that temporary link and add 2 to the ans list, as we now are to visit this root node. Then we move to the right child of 2, which is node 3. Now the ans list is [1, 2].

  4. At node 3, since there is no left child to process, we visit this node and add its value to the ans list. Now ans = [1, 2, 3].

  5. As there are no more unvisited nodes left, and the right child of 3 is None, the traversal is complete.

The final ans list is [1, 2, 3], which is indeed the inorder traversal of the given binary tree.

Note that during the entire process, no extra space was used for stack or recursion, and the tree's original structure was restored after it had been temporarily altered to maintain the traversal state.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
10        # Initialize the output list to store the inorder traversal
11        result = []
12      
13        # Continue traversing until there are no more nodes to process
14        while root:
15            # If there is no left child, add the current node's value to the result
16            # and move to the right child
17            if root.left is None:
18                result.append(root.val)
19                root = root.right
20            else:
21                # Find the rightmost node in the left subtree or the left child itself
22                # if it does not have a right child. This node will be our "predecessor"
23                predecessor = root.left
24                while predecessor.right and predecessor.right != root:
25                    predecessor = predecessor.right
26              
27                # If the predecessor's right child is not set to the current node,
28                # set it to the current node and move to the left child of the current node
29                if predecessor.right is None:
30                    predecessor.right = root
31                    root = root.left
32                else:
33                    # If the predecessor's right child is set to the current node,
34                    # it means we have processed the left subtree, so add the current
35                    # node's value to the result and sever the temporary link to restore
36                    # the tree structure. Then, move to the right child.
37                    result.append(root.val)
38                    predecessor.right = None
39                    root = root.right
40      
41        # Return the result of the inorder traversal
42        return result
43
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16
17class Solution {
18    public List<Integer> inorderTraversal(TreeNode root) {
19        // Initialize an empty list to store the inorder traversal result
20        List<Integer> result = new ArrayList<>();
21      
22        // Continue the process until all nodes are visited
23        while (root != null) {
24            // If there is no left child, visit the current node and go to the right child
25            if (root.left == null) {
26                result.add(root.val);
27                root = root.right;
28            } else {
29                // Find the inorder predecessor of the current node
30                TreeNode predecessor = root.left;
31                // Move to the rightmost node of the left subtree or
32                // the right child of the predecessor if it's already set
33                while (predecessor.right != null && predecessor.right != root) {
34                    predecessor = predecessor.right;
35                }
36                // If the right child of the predecessor is not set,
37                // this means this is our first time visit this node, thus,
38                // set the right child to the current node and move to the left child
39                if (predecessor.right == null) {
40                    predecessor.right = root;
41                    root = root.left;
42                } else {
43                    // If the right child is already set to the current node,
44                    // it means we are visiting the node the second time.
45                    // Thus, we should visit the current node and remove the link.
46                    result.add(root.val);
47                    predecessor.right = null;
48                    root = root.right;
49                }
50            }
51        }
52        // Return the completed list of nodes in inorder
53        return result;
54    }
55}
56
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    vector<int> inorderTraversal(TreeNode* root) {
16        vector<int> result;       // This vector will store the inorder traversal result.
17      
18        // Loop through all nodes of the tree using Morris Traversal technique.
19        while (root != nullptr) {
20            // If there is no left subtree, print the root and move to the right subtree.
21            if (!root->left) {
22                result.push_back(root->val); // Add the current node value.
23                root = root->right;          // Move to the right subtree.
24            } else {
25                // Find the inorder predecessor of the current root.
26                TreeNode* predecessor = root->left;
27              
28                // Navigate to the rightmost node of the left subtree or to the current root
29                // if the link is already established.
30                while (predecessor->right != nullptr && predecessor->right != root) {
31                    predecessor = predecessor->right;
32                }
33              
34                // Establish a link from the predecessor to the current root, if it does not exist.
35                if (!predecessor->right) {
36                    predecessor->right = root; // Link predecessor to the root.
37                    root = root->left;         // Move root to its left child.
38                } else {
39                    // A link from the predecessor to the current root already exists,
40                    // which means we have finished processing the left subtree.
41                    result.push_back(root->val); // Add the value of the current node.
42                    predecessor->right = nullptr; // Remove the link to restore tree structure.
43                    root = root->right;           // Move to the right subtree.
44                }
45            }
46        }
47        return result; // Return the result vector containing the inorder traversal.
48    }
49};
50
1// Definition for a binary tree node.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Performs an inorder traversal of a binary tree.
10 * @param {TreeNode | null} root - The root node of the binary tree.
11 * @returns {number[]} - An array of node values in the inorder sequence.
12 */
13function inorderTraversal(root: TreeNode | null): number[] {
14    // Base case: if the current root is null, return an empty array.
15    if (root === null) {
16        return [];
17    }
18
19    // Recursive case:
20    // 1. Traverse the left subtree and collect the values.
21    // 2. Include the value of the current node.
22    // 3. Traverse the right subtree and collect the values.
23    // Then concatenate them in inorder sequence.
24    return [
25        ...inorderTraversal(root.left), // Left subtree values
26        root.val,                      // Current node value
27        ...inorderTraversal(root.right) // Right subtree values
28    ];
29}
30
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

The code implements the Morris In-order Traversal algorithm for a binary tree. Let's analyze both the time and space complexity:

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree. Each node gets visited exactly twice in the worst case, once to establish the temporary link to its in-order predecessor and once to remove it and visit the node itself. The otherwise O(n) traversal is not affected by this temporary linking as it only adds a constant amount of work for each node.

Space Complexity

The space complexity of the algorithm is O(1). Unlike traditional in-order traversal using recursion (which could lead to O(h) space complexity where h is the height of the tree due to the call stack), the Morris Traversal does not use any additional space for auxiliary data structures such as stacks or recursion. It uses the given tree's null right pointers to temporarily store the successors of nodes, thereby using the tree itself to guide the traversal.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ