Select topics to narrow your question pool, then enable Random to jump to a random question matching your filters.

Python Quiz #52

Why In-Order Comes Out Sorted

easyData Structures & Algorithms

In a binary search tree every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger. Why does an in-order traversal (left subtree, node, right subtree) print the keys in sorted order, as the program below shows?

📄 Code

1class Node:
2    def __init__(self, key: int) -> None:
3        self.key = key
4        self.left = None
5        self.right = None
6 
7 
8def insert(node, key: int):
9    if node is None:
10        return Node(key)
11    if key < node.key:
12        node.left = insert(node.left, key)
13    else:
14        node.right = insert(node.right, key)
15    return node
16 
17 
18def in_order(node) -> None:
19    if node is not None:
20        in_order(node.left)
21        print(node.key, end=" ")
22        in_order(node.right)
23 
24 
25root = None
26for key in [50, 30, 70, 20, 40]:
27    root = insert(root, key)
28in_order(root)
29print()