Python binary search trees

Insert ordered keys and traverse them in sorted order.

Python

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

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

def inorder(root, values):
    if root is not None:
        inorder(root.left, values)
        values.append(root.value)
        inorder(root.right, values)

root = None
for value in [4, 2, 6, 1, 3]:
    root = insert(root, value)
values = []
inorder(root, values)
print(values)
assert values == [1, 2, 3, 4, 6]

Output

[1, 2, 3, 4, 6]

Explanation

In this tree, smaller values go left and larger values go right. Equal values are ignored, giving set-like behavior.

An inorder traversal visits left subtree, node, then right subtree. The ordering invariant makes its result ascending. This is an unbalanced tree, so sorted insertions can form a long chain.

Explore the dry run

Guided walkthroughReady

1class Node:

2 def __init__(self, value):

3 self.value = value

4 self.left = self.right = None

6def insert(root, value):

7 if root is None:

8 return Node(value)

9 if value < root.value:

10 root.left = insert(root.left, value)

11 elif value > root.value:

12 root.right = insert(root.right, value)

13 return root

15def inorder(root, values):

16 if root is not None:

17 inorder(root.left, values)

18 values.append(root.value)

19 inorder(root.right, values)

21root = None

22for value in [4, 2, 6, 1, 3]:

23 root = insert(root, value)

24values = []

25inorder(root, values)

26print(values)

27assert values == [1, 2, 3, 4, 6]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Start an empty tree.	`root = None`	—
Insert 4 as root, 2 to its left, and 6 to its right.	`4: left=2, right=6`	—
Insert 1 left of 2 and 3 right of 2.	`2: left=1, right=3`	—
Descend left from 4 through 2 to 1.	`2: left=1, right=3`	—
Visit nodes in order: 1, 2, 3, 4, 6.	`values = [1, 2, 3, 4, 6]`	—
Print the ordered traversal.	`values = [1, 2, 3, 4, 6]`	[1, 2, 3, 4, 6]

Cost and common mistakes

Insertion is O(h) for height h, worst-case O(n). Traversal is O(n), using O(h) call stack plus O(n) output.

A binary search tree is not necessarily balanced.
The returned root must be assigned when inserting into an empty subtree.

Try it yourself

Insert 5 and 4 after the existing values.

Reveal answer and reasoning

5 becomes the left child of 6; duplicate 4 is ignored. Inorder becomes [1, 2, 3, 4, 5, 6].

Python binary search trees

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading