Python · Course navigation

Tutorials/Python/Lesson 31

Python binary search trees

Insert ordered keys and traverse them in sorted order.

On this page

Before you start

Recursion and node objects.

Insert ordered keys and traverse them in sorted order.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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].