Binary Tree and Traversals

CSC-211 · Semester III · Data Structures and Algorithms

intermediate30 minAvailable

Binary search treeOrdered structure · balanced by design

Nodes

Height

3levels

Active

—

Lab brief

Objective

Build a binary search tree by inserting values and compare inorder, preorder and postorder traversal orders.

Theory & concepts

A binary search tree keeps smaller values in the left subtree and larger values in the right subtree of every node. Insertion walks down comparing against each node, taking O(h) where h is the height. Traversals visit every node once: inorder visits left, node, right (yielding sorted order); preorder visits node, left, right; postorder visits left, right, node.

Rendering diagram…

BST insertion and traversal orders

Insert 50, 30, 70, 20, 40, 60, 80 → balanced BST
Inorder   → 20 30 40 50 60 70 80   (sorted)
Preorder  → 50 30 20 40 70 60 80
Postorder → 20 40 30 60 80 70 50
Search    → O(h); balanced tree h ≈ log n

Prerequisites

Lab: Recursion — Factorial and Fibonacci
Ordered comparisons

Instructions

1Insert values and watch each one find its position in the tree.
2Run the inorder traversal and note it produces sorted order.
3Compare preorder and postorder sequences with inorder.
4Search for a value and follow the left/right decisions down the tree.

Tasks

Insert order
Insert the sample values and confirm the tree shape.
Inorder = sorted
Verify the inorder output is ascending.
Root positions
State which node is first in preorder and last in postorder, and why.

Self-check

Insertions maintain the BST ordering invariant.
Inorder output is correctly sorted.
The three traversal rules are applied correctly.

Environment

tree canvasinsertsearchinorderpreorderpostorder