Skip to main content

Binary tree traversals; preorder of BST

Short answer

Preorder visits root, left subtree, right subtree (NLR); inorder (LNR) gives sorted order for BST; postorder (LRN) visits children before root. For the BST built from 20,10,18,4,8,5,13,16,47,1,27, the preorder sequence is 20, 10, 4, 1, 8, 5, 18, 13, 16, 47, 27.

Explain different traversal methods for a binary tree. What will be the result of pre-order traversal for given binary search tree with nodes: 20, 10, 18, 4, 8, 5, 13, 16, 47, 1, and 27?

A traversal visits every node of a binary tree exactly once. The three depth-first methods differ in when the root is visited (L = left, R = right, N = node/root).

TraversalOrderRule
PreorderN L Rvisit root, traverse left subtree, traverse right subtree
InorderL N Rtraverse left subtree, visit root, traverse right subtree
PostorderL R Ntraverse left subtree, traverse right subtree, visit root
void preorder(struct node *p)  { if (p) { printf("%d ", p->info); preorder(p->left); preorder(p->right); } }
void inorder(struct node *p)   { if (p) { inorder(p->left); printf("%d ", p->info); inorder(p->right); } }
void postorder(struct node *p) { if (p) { postorder(p->left); postorder(p->right); printf("%d ", p->info); } }

Level-order (breadth-first) traversal using a queue is a fourth method.

Example for tree A(B,C): preorder A B C, inorder B A C, postorder B C A.

Preorder of the given BST

Insert 20, 10, 18, 4, 8, 5, 13, 16, 47, 1, 27 in order:

20
├─L:10
│  ├─L:4
│  │  ├─L:1
│  │  └─R:8
│  │     └─L:5
│  └─R:18
│     └─L:13
│        └─R:16
└─R:47
   └─L:27

Preorder (root, left, right):

20, 10, 4, 1, 8, 5, 18, 13, 16, 47, 27

(Inorder check: 1, 4, 5, 8, 10, 13, 16, 18, 20, 27, 47, which is sorted, so the tree is correct.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →