Inorder Traversal of a Binary Tree using Recursion

Problem Statement❯

Given the root of a binary tree, perform an inorder traversal using recursion and return the list of values in inorder sequence. Inorder traversal visits the left subtree first, then the root node, and finally the right subtree.

Examples❯

Input Tree	Inorder Output	Description
[1, 2, 3, 4, 5, null, 6]	[4, 2, 5, 1, 3, 6]	Standard binary tree with full left subtree and partial right subtree
[1]	[1]	Edge case: Tree with only a root node
[]	[]	Edge case: Empty tree (no nodes present)
[1, 2, null, 3, null, null, null, 4]	[4, 3, 2, 1]	Deep left-skewed binary tree
[1, null, 2, null, null, null, 3]	[1, 2, 3]	Right-skewed tree: Only right children present

Visualization Player

Solution❯

Case 1: Normal Binary Tree

In this case, the tree has both left and right subtrees. The recursive inorder traversal will visit the left subtree first, collect its values, then add the value of the root node, and finally visit the right subtree. For example, in a tree like:
1 / \ 2 3 / \ 4 5,
the order will be [4, 2, 1, 3, 5].

Case 2: Left Skewed Tree

All nodes are in the left direction, like a linked list bending left. The traversal will move to the deepest left node first and then backtrack. For example, 3 → 2 → 1 will be returned as [3, 2, 1].

Case 3: Right Skewed Tree

This time all nodes are connected on the right side. The recursion will print the root node first, and then recursively the right subtree. For instance, 1 → 2 → 3 will produce [1, 2, 3].

Case 4: Single Node Tree

If the tree has only one node, there are no left or right children. So the result of inorder traversal will simply be a list with the root node value. E.g., [1].

Case 5: Empty Tree

This is a boundary condition. If the input tree is null or empty, the recursive function will immediately return an empty list []. This ensures our function handles edge cases gracefully without errors.

Algorithm Steps❯

Start with the root node of the binary tree.
If the tree is empty, return an empty result.
Recursively perform inorder traversal on the left subtree.
Visit the current node and record its value.
Recursively perform inorder traversal on the right subtree.
Combine the results to produce the final inorder sequence.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

def inorderTraversal(root):
    if not root:
        return []
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(inorderTraversal(root))

⬅ Previous TopicPreorder Traversal of a Binary Tree using Iteration

Next Topic ⮕Inorder Traversal of a Binary Tree using Iteration

Comments

Loading comments...