Operations in Binary Tree

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Operations in Binary Tree

A binary tree's one defining rule: no node may have more than two children.

balanced ≈ log₂n comparisons · degenerate = n With n = 100, bal = 6.64, deg = 100.

At n = 1000 the balanced tree needs about 10 comparisons and the degenerate one needs 1000 — same data, same code, only the insertion order differed.

A Binary Search Tree (BST) adds a crucial ordering rule on top: for every node, everything in its LEFT subtree is smaller, and everything in its RIGHT subtree is larger. This ordering is exactly what makes searching fast.

💡 One-liner: "What property makes a BST searchable in roughly O(log n) time (for a balanced tree)?" → At each node, you can eliminate an entire half of the remaining tree by comparing against just that one node — same core idea as binary search on a sorted array.

The catch: O(log n) is a property of balance, not of BSTs

The elimination argument is right, but it assumes each comparison discards roughly half the remaining nodes. That is only true if the tree is reasonably balanced — and nothing in the BST rules enforces it.

Insert keys in already-sorted order and every new key goes to the right of the last one. The tree becomes a single right-hand spine — structurally a linked list wearing tree notation. Search degrades to O(n), and the ordering property is still perfectly satisfied.

💡 This is the exam's favourite trap: "insert 1,2,3,4,5 into an empty BST and give its height." The answer is 4, not 2. Drawing it out is the fastest way to see it, and sorted input is exactly the case that arises when someone loads a tree from an ordered file.

The three operations, and where the work is

🌳 Search, insert, delete

SearchCompare, go left or right, repeat. Cost is the height of the tree — not the node count.

InsertSearch for where the key would be; it is always added as a new leaf, so the shape depends entirely on insertion order.

DeleteThe awkward one — three cases below.

Deletion is where marks are won. A leaf is simply removed. A node with one child is replaced by that child. A node with two children cannot just be removed without orphaning a subtree — so it is replaced by its in-order predecessor or successor (the largest key on the left, or the smallest on the right), which is the only value that preserves the ordering property for every remaining node.

💡 Why the successor specifically? Because it is the next key in sorted order, so every key in the left subtree is still smaller than it and every key in the right subtree is still larger. Any other choice breaks the BST property somewhere.

Syllabus points

Binary tree / BST operations

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.