Inorder binary-tree traversal
Return the values of a binary tree in left-subtree, root, right-subtree order.
Course progress
Problem 46 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
BST values = [4, 2, 5, 1, 3]
Expected output
1 2 3 4 5
What is happening?
Visiting each left subtree, then the node, then its right subtree yields 1, 2, 3, 4, 5.
Solution strategy
Build the right mental model
Recursively visit the left child, record the current node, then visit the right child. A binary search tree is produced in sorted order.
Core concepts
binary tree · depth-first search
Complexity
Time O(n), space O(n) for the result plus O(h) call-stack space.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for inorder-tree-traversal
using System;
using System.Collections.Generic;
class Program
{
class Node
{
public int Value { get; private set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value) { Value = value; }
}
static void Traverse(Node node, List<int> values)
{
if (node == null) return;
Traverse(node.Left, values);
values.Add(node.Value);
Traverse(node.Right, values);
}
static void Main()
{
Node root = new Node(4);
root.Left = new Node(2);
root.Right = new Node(5);
root.Left.Left = new Node(1);
root.Left.Right = new Node(3);
var values = new List<int>();
Traverse(root, values);
Console.WriteLine(string.Join(" ", values));
}
}Knowledge check
Questions students often ask
What is the main idea behind inorder binary-tree traversal?
Recursively visit the left child, record the current node, then visit the right child. A binary search tree is produced in sorted order.
What is the time and space complexity of this solution?
Time O(n), space O(n) for the result plus O(h) call-stack space.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.