In-order List

The in-order list algorithm records binary tree vertices in the order: left subtree → vertex → right subtree. On a BST it produces a sorted list!

Sredni

O(V)O(V)OIJOI

Select programming language

Choose the language to see the in-order list implementation.

Select example

Small, Medium, and Large show recursion code generation. Very large shows only the call stack.

In-order List (Python): Small BST (5 nodes, BST)

Graph

1/0

Animation speed1.0x

Source codePython
1tree = {
2    1: [None, None],
3    3: [1, 6],
4    6: [None, None],
5    8: [3, 10],
6    10: [None, None]
7}
8in_order = []
9
10def dfs(vertex):
11    """In-order traversal of BST."""
12    if vertex is None:
13        return
14    left = tree[vertex][0]
15    right = tree[vertex][1]
16    dfs(left)
17    in_order.append(vertex)
18    dfs(right)
19
20dfs(8)
21print(f"In-order list: {in_order}")

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	tree = {
2	1: [None, None],
3	3: [1, 6],
4	6: [None, None],
5	8: [3, 10],
6	10: [None, None]
7	}
8	in_order = []
9
10	def dfs(vertex):
11	"""In-order traversal of BST."""
12	if vertex is None:
13	return
14	left = tree[vertex][0]
15	right = tree[vertex][1]
16	dfs(left)
17	in_order.append(vertex)
18	dfs(right)
19
20	dfs(8)
21	print(f"In-order list: {in_order}")