Binary Tree Inorder Traversal LeetCode Solution

Last updated on January 29th, 2025 at 02:18 am

Here, we see a Binary Tree Inorder Traversal LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, Stack, Tree

Companies

Microsoft

Level of Question

Easy

Binary Tree Inorder Traversal LeetCode Solution

Binary Tree Inorder Traversal LeetCode Solution

1. Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided code snippets is Tree Depth First Search (DFS). Specifically, it is an Inorder Traversal of a binary tree, which visits nodes in the order: Left -> Root -> Right. This traversal is implemented either iteratively (using a stack) or recursively.

3. Code Implementation in Different Languages

3.1 Binary Tree Inorder Traversal C++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> todo;
        while (root || !todo.empty()) {
            while (root) {
                todo.push(root);
                root = root -> left;
            }
            root = todo.top();
            todo.pop();
            nodes.push_back(root -> val);
            root = root -> right;
        }
        return nodes;
    }        
};

3.2 Binary Tree Inorder Traversal Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    dfsTraversal(list, root);
    return list;
}

private boolean dfsTraversal(List<Integer> list, TreeNode root) {
    if(root == null){
        return true;
    }
    if(dfsTraversal(list, root.left)){
        list.add(root.val);
    }
    return dfsTraversal(list, root.right);   
    }
}

3.3 Binary Tree Inorder Traversal JavaScript

var inorderTraversal = function(root) {
  const stack = [];
  const res = [];

  while (root || stack.length) {
    if (root) {
      stack.push(root);
      root = root.left;
    } else {
      root = stack.pop();
      res.push(root.val);
      root = root.right;
    }
  }
  return res;    
};

3.4 Binary Tree Inorder Traversal Python

class Solution(object):
    def inorderTraversal(self, root):
        result, stack = [], [(root, False)]

        while stack:
            cur, visited = stack.pop()
            if cur:
                if visited:
                    result.append(cur.val)
                else:
                    stack.append((cur.right, False))
                    stack.append((cur, True))
                    stack.append((cur.left, False))

        return result

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(h)
JavaO(n)O(h)
JavaScriptO(n)O(h)
PythonO(n)O(h)

where,
n is the number of nodes in the binary tree.
h is the height of the binary tree. In the worst case (skewed tree), h = n. In the best case (balanced tree), h = log(n).

  • The time complexity is O(n) because each node is visited exactly once.
  • The space complexity is O(h) because the stack (or recursion stack) stores at most h nodes at any given time.
Scroll to Top