Tree Algorithms

Overview

This subpackage provides the four classic traversals of a binary tree, and two functions about its shape: a balance check and the rebalancing of a binary search tree. Each traversal takes the tree itself and yields the data stored in its nodes, one at a time:

Function

Order

Typical use

preorder()

node, left, right

copying a tree, prefix expressions

inorder()

left, node, right

sorted output of a search tree

postorder()

left, right, node

freeing a tree, postfix expressions

level_order()

level by level, left to right

printing by depth, breadth-first search

They accept any AbstractBinaryTree (BinaryTree, BinarySearchTree, AVLTree, RedBlackTree) and walk it only through tree.root and tree.children(node). That accessor reports absent children as None whatever the implementation, so the sentinel leaves of a Red-Black tree never show up in the output.

Note

These functions replace the inorder_traversal(), preorder_traversal(), postorder_traversal() and level_order_traversal() methods, deprecated since 0.7.0 and scheduled for removal in 1.0.0:

tree.inorder_traversal()     # deprecated
inorder(tree)                # replacement

Iterating over a tree directly (for item in tree) is unaffected and still yields the items in inorder.

The Four Orders

        graph TD
    A((10)) --> B((5))
    A --> C((15))
    B --> D((3))
    B --> E((7))
    C --> F((12))
    C --> G((20))

    style A fill:#3498db,color:#fff
On the binary search tree above

Traversal

Sequence

preorder

10, 5, 3, 7, 15, 12, 20

inorder

3, 5, 7, 10, 12, 15, 20 (ascending, as for every search tree)

postorder

3, 7, 5, 12, 20, 15, 10

level_order

10, 5, 15, 3, 7, 12, 20

The three depth-first orders can be defined recursively. For a tree \(T\) with root \(r\) and subtrees \(L\) and \(R\):

\[\mathrm{pre}(T) = r \cdot \mathrm{pre}(L) \cdot \mathrm{pre}(R) \qquad \mathrm{in}(T) = \mathrm{in}(L) \cdot r \cdot \mathrm{in}(R) \qquad \mathrm{post}(T) = \mathrm{post}(L) \cdot \mathrm{post}(R) \cdot r\]

The implementations are iterative, with an explicit stack instead of recursion. The visiting order is the same, but a degenerate tree (for instance a search tree built from already sorted values, whose height equals its size) is no longer limited by Python’s recursion depth.

Complexity

Traversal

Time

Extra space

preorder, inorder, postorder

\(O(n)\)

\(O(h)\), \(h\) the height (\(\log n\) to \(n\))

level_order

\(O(n)\)

\(O(w)\), \(w\) the widest level (up to about \(n/2\))

is_balanced

\(O(n)\)

\(O(h)\)

rebalance

\(O(n \log n)\)

\(O(n)\)

Detailed Documentation

sds.algorithms.tree_algorithms.inorder(tree)[source]

Yield the items of a binary tree in inorder (left, node, right).

On a binary search tree, inorder visits the items in ascending order.

Parameters:

tree (AbstractBinaryTree) – The tree to traverse.

Yields:

Any – The data of each node, in inorder.

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in (10, 5, 15, 3, 7):
...     bst.insert(value)
>>> list(inorder(bst))
[3, 5, 7, 10, 15]

Notes

Time complexity: O(n). Space complexity: O(h), with h the height of the tree (the stack holds the path from the root to the current node).

The stack stores the ancestors whose left subtree is being visited:

node <- root
while stack or node:
    while node: push node; node <- left(node)
    node <- pop(); emit node; node <- right(node)
sds.algorithms.tree_algorithms.preorder(tree)[source]

Yield the items of a binary tree in preorder (node, left, right).

Parameters:

tree (AbstractBinaryTree) – The tree to traverse.

Yields:

Any – The data of each node, in preorder.

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in (10, 5, 15, 3, 7):
...     bst.insert(value)
>>> list(preorder(bst))
[10, 5, 3, 7, 15]

Notes

Time complexity: O(n). Space complexity: O(h).

The right child is pushed before the left one so that the left subtree, popped first, is visited first.

sds.algorithms.tree_algorithms.postorder(tree)[source]

Yield the items of a binary tree in postorder (left, right, node).

Parameters:

tree (AbstractBinaryTree) – The tree to traverse.

Yields:

Any – The data of each node, in postorder.

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in (10, 5, 15, 3, 7):
...     bst.insert(value)
>>> list(postorder(bst))
[3, 7, 5, 15, 10]

Notes

Time complexity: O(n). Space complexity: O(h).

A node is emitted only once its right subtree is done, which the loop detects by remembering the last node emitted: if it is the right child of the node on top of the stack (or there is no right child), that node’s turn has come.

sds.algorithms.tree_algorithms.level_order(tree)[source]

Yield the items of a binary tree level by level (breadth-first).

Nodes of depth d all come before nodes of depth d + 1; within a level, nodes appear from left to right.

Parameters:

tree (AbstractBinaryTree) – The tree to traverse.

Yields:

Any – The data of each node, level by level.

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in (10, 5, 15, 3, 7):
...     bst.insert(value)
>>> list(level_order(bst))
[10, 5, 15, 3, 7]

Notes

Time complexity: O(n). Space complexity: O(w), with w the largest number of nodes on one level (up to about n/2 for a complete tree).

Balance

A binary tree is height-balanced when, at every node, the heights of the two subtrees differ by at most one (the AVL criterion). Its height is then \(O(\log n)\), which keeps searches logarithmic.

A plain BinarySearchTree does not stay balanced by itself: inserting sorted values builds a chain. rebalance() rebuilds such a tree in place from its sorted content, inserting the median first, then the medians of each half, level by level:

        graph LR
    subgraph "Before: insert 1..7 in order"
    A1((1)) --> A2((2)) --> A3((3)) --> A4((4)) --> A5((5)) --> A6((6)) --> A7((7))
    end

    subgraph "After rebalance()"
    B4((4)) --> B2((2))
    B4 --> B6((6))
    B2 --> B1((1))
    B2 --> B3((3))
    B6 --> B5((5))
    B6 --> B7((7))
    end

    style B4 fill:#2ecc71,color:#fff

The result has the minimum possible height, \(\lfloor \log_2 n \rfloor\), for distinct keys. The self-balancing AVLTree and RedBlackTree are not accepted: they repair their shape with rotations on every update, and those rotations stay inside their classes as part of their invariant.

sds.algorithms.tree_algorithms.is_balanced(tree)[source]

Return True if the tree is height-balanced (AVL criterion).

Parameters:

tree (AbstractBinaryTree) – Any binary tree.

Returns:

True if, at every node, the heights of the two subtrees differ by at most one. An empty tree is balanced.

Return type:

bool

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in (1, 2, 3):
...     bst.insert(value)
>>> is_balanced(bst)
False
>>> rebalance(bst)
>>> is_balanced(bst)
True

Notes

Time complexity: O(n). Space complexity: O(h).

Heights are computed bottom-up in a single iterative postorder pass, so a degenerate tree of any depth is handled. An AVLTree always passes this check; a RedBlackTree need not, since its own balance rule is looser (the longest path is at most twice the shortest).

sds.algorithms.tree_algorithms.rebalance(tree)[source]

Rebuild a binary search tree into a height-balanced shape, in place.

The tree keeps the same items and the same identity: only its shape changes. Afterwards its height is floor(log2 n) when the keys are distinct.

Parameters:

tree (BinarySearchTree) – The tree to rebalance. It is modified in place.

Raises:

StructureTypeError – If tree is not a BinarySearchTree. AVLTree and RedBlackTree are rejected too: they keep themselves balanced.

Examples

>>> from sds.tree import BinarySearchTree
>>> bst = BinarySearchTree()
>>> for value in range(1, 8):          # sorted input: a chain
...     bst.insert(value)
>>> bst.height()
6
>>> rebalance(bst)
>>> bst.height()
2
>>> list(bst)
[1, 2, 3, 4, 5, 6, 7]

Notes

Time complexity: O(n log n): one inorder pass, then n insertions into a tree whose height never exceeds log2 n. Space complexity: O(n) for the sorted copy of the items.

The parameter is narrowed to the concrete BinarySearchTree (#86): rebalancing needs the search-tree ordering of insert(), which the AbstractBinaryTree interface does not promise (BinaryTree inserts level by level).

The rebuild only uses the tree’s public interface (clear() and insert()). An O(n), O(1)-space alternative exists, the Day-Stout-Warren algorithm, but it rewires node links directly, which would mean reaching into the structure’s internals.

BinarySearchTree sends duplicates to the right subtree, so a tree with many equal keys cannot reach minimum height whatever its shape; the items are still all kept, in order.

Usage Example

from sds.tree import AVLTree
from sds.algorithms.tree_algorithms import inorder, level_order

tree = AVLTree()
for value in range(1, 8):       # sorted input: the AVL tree rebalances
    tree.insert(value)

list(inorder(tree))              # [1, 2, 3, 4, 5, 6, 7]
list(level_order(tree))          # [4, 2, 6, 1, 3, 5, 7]

# Traversals are lazy: stop as soon as the answer is known
first_even = next(x for x in inorder(tree) if x % 2 == 0)

References