Inorder traversal and ordered queries

What is a binary search tree?

A binary search tree, or BST, is a binary tree with an ordering rule. In the unique-key version here, every value in a node’s left subtree is smaller than that node, and every value in its right subtree is larger. This rule tells a search which direction to follow.

Example: At a node containing 8, search for 4 by moving left. Search for 12 by moving right. Search speed depends on height: an unbalanced tree can become a long chain.

Helpful before this chapter

If these ideas are new, begin with:

Binary trees

Understand the idea

Inorder traversal exposes sorted keys. Predecessor, successor, rank, and range queries exploit order; rank can be logarithmic with subtree sizes in a balanced tree, rather than scanning the entire traversal.

Work through an example

Keys [1,2,3,4,6] give predecessor of 4 as 3 and successor as 6. A range query can prune subtrees outside [lo,hi].

Time and space complexity

Traversal O(n); kth via scan O(h+k); augmented balanced rank O(log n).

Why it works

Inorder emits all left keys, then root, then all right keys in ascending order.

Common mistakes

A heap does not provide sorted inorder.
Forgetting to update subtree sizes corrupts rank queries.

Chapter lab · Python implementation

A strict BST stores smaller keys left and larger keys right. This chapter assumes unique keys; duplicate-key policies need explicit changes. Operations follow one root-to-leaf path, so their cost is proportional to height. Balancing is what turns that into a logarithmic worst-case guarantee.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Node:
    def __init__(self,key):
        self.key,self.left,self.right=key,None,None

def insert(root,key):
    if root is None: return Node(key)
    if key<root.key: root.left=insert(root.left,key)
    elif key>root.key: root.right=insert(root.right,key)
    return root

def search(root,key):
    while root is not None:
        if key==root.key: return root
        root=root.left if key<root.key else root.right
    return None

def valid(root,low=float('-inf'),high=float('inf')):
    if root is None: return True
    return (low<root.key<high and
            valid(root.left,low,root.key) and
            valid(root.right,root.key,high))

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=None
for x in [4,2,6,1,3]: root=insert(root,x)
assert valid(root) and search(root,3).key==3
assert search(root,9) is None
root.left.right.key=5; assert not valid(root)

CHECK YOUR UNDERSTANDING