Abdu's Garden

Trees - The CompSci kind

Properties1
tagstrees, datastructure

7 min read

Intro

A common abstractdatatype representing connected, acyclic graphs.
Cyclic trees are called Graphs.
Remember All trees are graphs, but not all graphs are trees…
Often although not necessarily, Trees have a root node, and end nodes known as leaves.
Each node in the tree can be connected to one or more children but only one parent, except the root which has no parent.

Representing data in a tree can speed up your algorithms in many natural problems.
Two common ways to represent graphs:

  1. Adjacency Matrix
    1. matrix i,e, a 2D array of cells, each representing an edge
    2. Cell i, j represents an edge from vertex i to j
  2. Adjacency Lists:
    1. linked lists – one for each vertex, showing all the neighbors of that vertex

There are many types of trees we’ve covered many in our comp3760 Algorithms course at BCIT.

Representing Trees

There are a few different ways of doing so. Some involve oop and others use fundamental data structures that can be found in most programming languages such as dictionaries and lists.

Node Class (OOP)

This is the typical representation you’ll encounter while studying and practicing.
Goes something like this:

# Python class for a typical 'Node' object
class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = No

Array of Arrays

Another way is using a 2-dimensional array (2D). Since each node has one parent, that’d be the outer array.
In this representation the structure is as follows:

  • The value of a node is the first element in the array.
  • The left subtree is the second element, which can be another array.
  • the right subtree is the third element and can also be another array.
    For example:
tree = [
    'a',  #root
    ['b',  # left subtree
        ['d' [], []],
        ['e' [], []]
    ],
    ['c',  # right subtree
        ['f' [], []],
        []
    ]
]

// I hate this

Accessing

Since it’s an array (or Python list in this example) we can access elements using regular indexing. For example root = tree[0]
and the left subtree of the root’s left subtree would be tree[1][1].

Tables/Maps

A table illustrates the nested nature of a tree much better than an array. In this representation, each node has 3 keys, val, left, and right. Obviously, the left and right keys are in turn representing another table with the same keys…
This ends up looking like a nested object (it kinda is) but thanks to Map and Table implementations.

my_tree = {
    'val': 'A',
    'left': {
        'val': 'B',
        'left': {'val': 'D'},
        'right': {'val': 'E'}
    },
    'right': {
        'val': 'C',
        'right': {'val': 'F'}
    }
}

Binary Trees

The most infamous type of trees in computer science. A binarytree is a tree that has left and right children.
In some Binary Trees, a node has a value, and the left child’s value is less than the parent’s and the right’s is greater. These are known as Binary Search Trees (BST)

// In all Binary Trees, the data must be ordered!

Terminology

  • Complete Binary Tree: one in which every level except the last is filled, and all nodes of the last level are to the far left as possible.
  • Balanced Binary Tree: one with a structure in which the height of the left and right sub-trees per node differ by 0 or 1.

Depth-First ( dfs )Traversal Methods

Unless specified, syntax isn't valid, only pseudocode!

In-order

Recursive

This is the standard recursive approach, simplified but the idea gets across:

//In-order implementation
void inorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
 
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}

Iterative

Simple Stack implementation, is time and space complexity.

def in_ord(root):
	if root is null:
		return
	
	stack = new Stack()
	curr = root
	
	while curr or stack not empty:
		# going down the tree
		while curr:
			# add to stack
			stack.push(curr)
			# go left
			curr = curr.left
		
		# curr is now null, end of subtree so pop from stack
		curr = stack.pop()
		# do something with "visited" node
		print(curr)
		# no more left subtree, check right
		curr = curr.right

Morris’ Traversal Algorithm

More optimized for In order traversal as it’s time but space since it doesn’t need a Stack.
Found this example on GeeksForGeeks example

We want to traverse the tree and come back to the root after finishing the left subtree, but without a stack. Morris Traversal achieves this by temporarily modifying the tree

  • For each node, check if it has a left child.
  • If it does not have a left child, visit it and move to the right child.
  • If it has a left child, find the inorder predecessor (rightmost node in the left subtree).
  • Make the current node as the right child of its inorder predece(1) ssor (temporary link).
  • Move to the left child.
  • When you encounter a temporary link again, it means the left subtree is fully visited:
    • Remove the temporary link.
    • Visit the current node.
    • Move to the right child.
def morris_inorder(root):
    res = []
    curr = root
 
    while curr is not None:
        if curr.left is None:
            # If no left child, visit this node then go right
            res.append(curr.data)
            curr = curr.right
        else:
            # Find the inorder predecessor of curr
            prev = curr.left
            while prev.right is not None and prev.right != curr:
                prev = prev.right
            # Make curr the right child of its inorder predecessor
            if prev.right is None:
                prev.right = curr
                curr = curr.left
            else:
                # Revert the changes made in the tree
                prev.right = None
                res.append(curr.data)
                curr = curr.right

Pre-order

Recursive approach

void preorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
printf("%d ", node->data);
preorderTraversal(node->left);
preorderTraversal(node->right);
}

Iterative approach

Tree parameter is root and not node since iterative…

def pre_ord(root):
	if root is null:
		return
		
	stack = new Stack(root)
	while stack not empty:
		curr = stack.pop()
		# do something
		print(curr)
		if curr.right exists stack.push(curr.right)
		if curr.left exists stack.push(curr.left)

Now this implementation pushes the left sub-tree onto the stack just to push it on the next loop, let’s optimize slightly

def pre_ord(root):
	if root is null:
		return
	stack = new Stack() #empty
	curr = root
	while curr not null and stack not empty:
		while curr:
			print(curr)
			if curr.right exists stack.push(curr.right)
			curr = curr.left
		if stack not empty:
			curr = stack.pop()

Post-order

Recursive

void postorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%d ", node->data);
}

Iterative 2 Stacks

This implementation uses two stacks, one to traverse all the way through, and another to form the results.

def post_ord(root):
	if root is null:
		return
	
	stack = new Stack(root) # this one init with root node
	output = new Stack() # this one's empty 
	while stack not empty:
		curr = stack.pop()
		# add the current to output stack
		output.push(curr)
		if curr.left exists stack.push(curr.left)
		if curr.right exists stack.push(curr.right)
	
	# now that everything's been stacked, we pop the post order 
	while output not empty:
	curr = output.pop()
		# do something
		print(curr)

Keep in Mind

In-Order traversal of a Binary Tree is insufficient to uniquely serialize a tree. Pre-Order or Post-Order traversal is also required for this.

Resources

Graph View

Backlinks