Trees

Properties of a Tree

• A tree is a node based data structure.

• Each node can have links to multiple other nodes

  • Compare this to a singly linked list which can only link to the next node or a double linked list which can only link to the previous and next nodes.

• All the nodes in a tree must be connected

• There cannot be any cycles in a tree (i.e. two nodes cannot link to the same child node)

• A tree is balanced when the following 3 conditions are met:

  • The left and right subtrees heights differ by at most 1

  • The left subtree is balanced

  • The right subtree is balanced

• A tree is perfectly balanced when the left and right subtrees of any node are the same height.

Example of a tree. This is NOT a binary tree as the 7 node has three child nodes. This is an imbalanced tree. Attribution: Paddy3118, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

Example of a balanced binary tree. Attribution: User:Mikm, Public domain, via Wikimedia Commons

Binary Tree

A binary tree is a tree where each node can have zero, one or two children.

Unbalanced and not sorted binary tree. Attribution: Radke7CB, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons

Binary Search Trees

A binary search tree is a binary tree that has these properties:

• Each node can have at most one left and one right child

• The left descendants must only contain values that are less than the node

• The right descendants must only contain values that are greater than the node

• Each subtree must be a valid binary search tree.

Deletion rules

• If the node to delete has no children, then just delete it

• If the node to delete has one child, delete the node, and put the child node where the deleted node was.

• If the node to delete has two children, then replace it with successor node. The successor node is the node with the least value of the child nodes that are greater than the deleted node.

  • To find the successor node: visit the right child of the deleted node. Traverse down the left branch of all child nodes until a node does not have a left child. That node is the successor node.

• If the successor node has a right child, then after placing the successor node in its new spot, move the right child to the left side of the successor's former parent

• Example of finding the successor node:

  • Suppose we want to delete 3 from the above diagram. We would delete the 3, then move to the right child, 6. We, then traverse down the left branches. In this case, there is only one, 4. Node 4, moves to where node 3 was.

Tree Traversal

Four ways to traverse a tree are:

• Preorder

• Inorder

• Postorder

• Level order

The first 3 traversals (preorder, inorder and postorder) use Depth First Search to traverse the tree. Where the node is processed in relation to traversing the children determines the type of traversal. Level order traversal uses Breadth First Search to traverse the tree.

Preorder

The tree is traversed in the order: Node -> Left -> Right

Using the above binary search tree structure, the result of a preorder traversal would be:

8, 3, 1, 6, 4, 7, 10, 14, 13

Using preorder traversal means the root node will be processed first.

def preorder(tree: TreeNode):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

Inorder

The tree is traversed in the order: Left -> Node -> Right

Using the above binary search tree structure, the result of an inorder traversal would be:

1, 3, 4, 6, 7, 8, 10, 13, 14

Using inorder traversal on a binary search tree will traverse the nodes in ascending order.

def inorder(tree: TreeNode):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)
    

Postorder

The tree is traversed in the order: Left -> Right -> Node

Using the above binary search tree structure, the result of an inorder traversal would be:

1, 4, 7, 6, 3, 13, 14, 10, 8

Using postorder traversal means the root node will be processed last.

def postorder(tree: TreeNode):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)
    

Level-order

The tree is traversed level by level: Level 0 -> Level 1 -> Level 2 etc

Using the above binary search tree structure, the result of a level traversal would be:

8, 3, 10, 1, 6, 14, 4, 7, 13

def level_order(tree: TreeNode) -> List:
    queue = deque()
    result = []
    queue.append(tree)
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.value)
            queue.append(node.left)
            queue.append(node.right)
    return result

Trie

• A kind of tree that is good for text-based features such as autocomplete

• It is NOT a binary tree. It can have multiple child nodes.