Problem

Given a binary search tree (aka an “ordered binary tree”), iterate over the nodes to print them out in increasing order. So the tree…

Examples

Example 1:

1
2
3
4
5

       4
      / \
     2   5
    / \
   1   3

1
2
3

Input:
root = [4, 2, 5, 1, 3]
Output: [1, 2, 3, 4, 5]

Solution

Method 1 - Inorder traversal

This solution is same as inorder traversal in any binary tree. We have seen it here.

Code

1
2
3
4
5
6

void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ", root->val);
  inorderTraversal(root->right);
}
1
2
3
4
5
6
7
8

public void inorderTraversal(TreeNode root) {
	if (root == null) {
		return;
	}
	inorderTraversal(root.left);
	System.out.println(root.val + " ");
	inorderTraversal(root.right);
}

Complexity

  • ⏰ Time complexity: O(n) as we traverse all nodes in tree.
  • 🧺 Space complexity: O(1) assuming we are not using extra space in recursion stack.