Binary Tree Inorder Traversal

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes?

The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5.

The definition of a tree node is as follows:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

public class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

struct Node {
  int val;
  Node* left = nullptr;
  Node* right = nullptr;

  Node(int val) : val(val) {}
};

public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

type Node struct {
    val   int
    left  *Node
    right *Node
}

func newNode(val int) *Node {
    return &Node{val, nil, nil}
}

Follow up: you'll likely get the recursive solution first, could you do it iteratively?

Constraints

Number of vertices in the tree <= 100000
The values of the vertices in the tree will be between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

```js
function inorderTraversal(root) {
  return root;
};
```
java
```java
public List<Integer> inorderTraversal(TreeNode root) {
  return root;
}
```
```csharp
public List<int> InorderTraversal(TreeNode root) {
  return root;
}
```
```cpp
vector<int> inorderTraversal(TreeNode* root) {
  return root;
}
```

Step Two

This is one of those questions where knowing the terminology is necessary. In-order traversal visits the left child nodes first, then the root, followed by the right child (remember, it's called in-order because the current node's value is read in-between the left and right child nodes).

Recall the following ordering types:

Inorder traversal

First, visit all the nodes in the left subtree
Then the root node
Visit all the nodes in the right subtree

When to use? With a BST, the in order traversal will give the elements in ascending order, useful for problems where order matters.

// pseudo-logic of the inorder function:
inorder(root.left)
display(root.data)
inorder(root.right)

```java
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    private static void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        List<Integer> res = inorderTraversal(root);
        System.out.println(res);
    }
}
```
```cpp
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void helper(TreeNode* root, vector<int>& res) {
    if (root) {
        if (root->left) {
            helper(root->left, res);
        }
        res.push_back(root->val);
        if (root->right) {
            helper(root->right, res);
        }
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    vector<int> res;
    helper(root, res);
    for(int i : res) {
        cout << i << " ";
    }
    cout << endl;
}
```
```csharp
using System;
using System.Collections.Generic;

public class MainClass {
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    
    public static void Helper(TreeNode root, List<int> res) {
        if (root != null) {
            if (root.left != null) {
                Helper(root.left, res);
            }
            res.Add(root.val);
            if (root.right != null) {
                Helper(root.right, res);
            }
        }
    }
    
    public static IList<int> InorderTraversal(TreeNode root) {
        List<int> res = new List<int>();
        Helper(root, res);
        return res;
    }

    public static void Main(string[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        IList<int> res = InorderTraversal(root);
        foreach (int i in res) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }
}
```
```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := &TreeNode{Val: 1}
	root.Right = &TreeNode{Val: 2}
	root.Right.Left = &TreeNode{Val: 3}
	res := inorderTraversal(root)
	fmt.Println(res)
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	helper(root, &res)
	return res
}

func helper(root *TreeNode, res *[]int) {
	if root != nil {
		if root.Left != nil {
			helper(root.Left, res)
		}
		*res = append(*res, root.Val)
		if root.Right != nil {
			helper(root.Right, res)
		}
	}
}
```
```javascript
function inorderTraversal(root) {
  let res = [];
  helper(root, res);
  return res;
}

function helper(root, res) {
  if (!root) {
    return res;
  }
  helper(root.left, res);
  res.push(root.val);
  helper(root.right, res);
  return res;
}

const root = {
  val: 1,
  right: {
    val: 2,
    left: {
      val: 3
    }
  }
};

console.log(inorderTraversal(root));
```
```python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def inorder(root):
    res = []
    helper(root, res)
    return res


def helper(root, res):
    if root:
        if root.left:
            helper(root.left, res)
        res.append(root.val)
        if root.right:
            helper(root.right, res)


if __name__ == "__main__":
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    print(inorder(root))
```

Step Three

Preorder traversal

Visit root node
Then go to all the nodes in the left subtree
Visit all the nodes in the right subtree

When to use? You can use pre-order traversal to create a copy of the tree, since you can access each node before its subtrees. It's also used to get expressions on an expression tree.

display(root.data)
preorder(root.left)
preorder(root.right)

Note: This algorithm is equivalent to the famous graph algorithm Depth First Search (DFS).

```java
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    private static void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        helper(root.left, res);
        helper(root.right, res);
    }

    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        List<Integer> res = preorderTraversal(root);
        System.out.println(res);
    }
}
```
```cpp
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void helper(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);
    helper(root->left, res);
    helper(root->right, res);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    vector<int> res;
    helper(root, res);
    for(int i : res) {
        cout << i << " ";
    }
    cout << endl;
}
```
```csharp
using System;
using System.Collections.Generic;

public class MainClass {
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    
    public static void Helper(TreeNode root, List<int> res) {
        if (root == null) return;
        res.Add(root.val);
        Helper(root.left, res);
        Helper(root.right, res);
    }
    
    public static IList<int> PreorderTraversal(TreeNode root) {
        List<int> res = new List<int>();
        Helper(root, res);
        return res;
    }

    public static void Main(string[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        IList<int> res = PreorderTraversal(root);
        foreach (int i in res) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }
}
```
```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	res := preorderTraversal(root)
	fmt.Println(res)
}

func preorderTraversal(root *TreeNode) []int {
	var res []int
	helper(root, &res)
	return res
}

func helper(root *TreeNode, res *[]int) {
	if root == nil {
        return
    }
    *res = append(*res, root.Val)
    helper(root.Left, res)
    helper(root.Right, res)
}
```
```javascript
function preorderTraversal(root) {
  let res = [];
  helper(root, res);
  return res;
}

function helper(root, res) {
  if (!root) {
    return res;
  }
  res.push(root.val);
  helper(root.left, res);
  helper(root.right, res);
  return res;
}

const root = {
  val: 1,
  left: {
    val: 2
  },
  right: {
    val: 3
  }
};

console.log(preorderTraversal(root));
```
```python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorder(root):
    res = []
    helper(root, res)
    return res

def helper(root, res):
    if root:
        res.append(root.val)
        if root.left:
            helper(root.left, res)
        if root.right:
            helper(root.right, res)

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    print(preorder(root))
```

Step Four

Postorder traversal

Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node

When to use? You can use post-order traversal to delete a tree, since you can delete all of a node's children before itself.

postorder(root.left)
postorder(root.right)
display(root.data)

```java
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    private static List<Integer> res = new ArrayList<>();
    private static void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);
        helper(root.right);
        res.add(root.val);
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        helper(root);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        List<Integer> res = postorderTraversal(root);
        System.out.println(res);
    }
}
```
```cpp
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> res;
void helper(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    helper(root->left);
    helper(root->right);
    res.push_back(root->val);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    helper(root);
    for(int i : res) {
        cout << i << " ";
    }
    cout << endl;
}
```
```csharp
using System;
using System.Collections.Generic;

public class Program {
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
    
    public static List<int> res = new List<int>();
    public static void Helper(TreeNode root) {
        if (root == null) {
            return;
        }
        Helper(root.left);
        Helper(root.right);
        res.Add(root.val);
    }

    public static IList<int> PostorderTraversal(TreeNode root) {
        Helper(root);
        return res;
    }

    public static void Main(string[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        IList<int> res = PostorderTraversal(root);
        foreach (int i in res) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }
}
```
```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var res []int

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	res = postorderTraversal(root)
	fmt.Println(res)
}

func postorderTraversal(root *TreeNode) []int {
	helper(root)
	return res
}

func helper(root *TreeNode) {
	if root == nil {
        return
    }
    helper(root.Left)
    helper(root.Right)
    res = append(res, root.Val)
}
```
```javascript
function postorderTraversal(root) {
  let res = [];
  helper(root, res);
  return res;
}

function helper(root, res) {
  if (!root) {
    return res;
  }
  helper(root.left, res);
  helper(root.right, res);
  res.push(root.val);
  return res;
}

const root = {
  val: 1,
  left: {
    val: 2
  },
  right: {
    val: 3
  }
};

console.log(postorderTraversal(root));
```
```python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def postorder(root):
    res = []
    helper(root, res)
    return res

def helper(root, res):
    if root:
        if root.left:
            helper(root.left, res)
        if root.right:
            helper(root.right, res)
        res.append(root.val)

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    print(postorder(root))
```

Complexity Analysis

Worst case scenario time complexity is O(n). Where n is the number of nodes in the tree (in the worst case, we'd need to go through every node to find the value we want).

As this is the recursive solution, it will require memory in the stack for each call of the traversal functions. So on average (balanced binary tree), the space complexity is O(logn). And in the worst case (skewed binary tree), the space complexity will be O(n).

For more information on tree complexities, check out our Big O Notation Cheat Sheet.

Note: Will the space complexity be same if we use an iterative solution for the traversal? Tell us in the discussion!

One Pager Cheat Sheet

Write a function to traverse a binary tree in-order and print the value of each node while it passes, while meeting the specified complexity requirements.
In-order traversal visits the left child nodes first, followed by the root, and then the right child, and is useful for obtaining ascending sorted order inBSTs.
Preorder traversal can be used to create a copy of the tree or to get expressions from an expression tree (equivalent to Depth First Search (DFS)) by displaying the root's data and then traversing its left and right subtrees.
With post-order traversal, display(root.data) will be called after traversing both left and right subtrees of the root node, which is useful for certain operations like tree deletion.
The worst case time complexity for a recursive tree traversal is O(n), and the corresponding space complexity is on average O(logn) (balanced binary tree) and O(n) (skewed binary tree).

Open interactive view →