DATA STRUCTURES
4.3 TREES

WHAT ARE TREES

Tree's are a visual representation of a hierarchical data structure to show how data is organised.  Tree structures are used in many different ways in computer systems, a well known tree structure method is the way your folders are structured on your drive or cloud storage.

In a 'Binary Tree' each point in a tree is called a node. Nodes can have a maximum of 1 link to a parent node(a node above) and a maximum of 2 links down to children nodes(nodes below).

A non-binary tree structure could have multiple nodes branching from a parent node, the same way a folder structure works.
​
A 'node' is a point in a system, for example this could be a point in a network or a position in an array highlighting, forming or representing a star point, end point or intersection.

​They are used extensively in programming and data structure. Binary trees can help with organising data for rapid access, such as in binary search trees or heaps, they are also used in algorithms that process trees, like syntax trees in compilers or HTML/XML parsing.

PARTS OF A TREE

ROOT: The node at the top of the tree
PARENT: Any node that has a child node below
LEFT-CHILD: The node on the left below a parent
RIGHT-CHILD: The node on the right below a parent
SUBTREE: A branch to the left or right of a parent that has at least one child of its own.
​LEAF: The last nodes at the bottom of the tree

TYPES OF TREES

There are 3 main types of Binary trees discussed at IB level,  Balanced Binary Trees, Unbalanced Binary Trees, Degenerate Trees. Here we take a look at each tree type.

BALANCED BINARY TREES
A balanced binary tree is a binary tree structure in which the left and the right subtrees of every node differ in height by no more than 1.

An example of a balanced binary tree is an AVL tree (named after inventors Adelson-Velsky and Landis). This is a self-balancing binary search tree, meaning it automatically maintains its height as minimal as possible whenever the tree is modified.

USE CASE: Balanced binary trees are very good for "dictionary" problems where the code inserts and looks up items by a key (like a map or a database index in programming), because the balance guarantees that the path to any leaf (which corresponds to a key lookup) is in O(log n), n being the number of nodes.

UNBALANCED BINARY TREES
An unbalanced binary tree is one where the distribution of nodes isn't even, causing the tree to lean to one side. This could be due to the nature of the data inserted into the tree or from deletions that leave one side of the tree sparse.

USE CASE: While unbalanced trees are generally inefficient compared to balanced trees, there can still be use cases for them. For example, if we are certain that our data will always be inserted in a certain order that keeps the tree relatively balanced, we might decide to use an unbalanced tree for simplicity.

DEGENERATE TREES
A degenerate tree is a tree where each parent node has only one associated child node. This effectively makes the tree perform like a linked list data structure.

USE CASE: Degenerate trees aren't typically used on purpose, as they have poor performance for most operations. However, they may result from certain sequences of operations on a binary tree. For example, continually adding nodes to only one side of the tree will result in a degenerate tree. As a linked list, though, they can be used for simple linear traversal.

These are some of the types of binary trees. Each has its own advantages, disadvantages, and specific use cases. It is crucial to use the right type of binary tree to suit your needs for efficient data storage and manipulation.

HOW BINARY TREES WORK

This video talks about Full Binary Tree's, Complete Binary Tree's and Prefect Binary Tree's. The video also looks at Balanced Binary Tree's, Un-balanced Binary Tree's and Degenerate Binary Tree's.

CREATING A TREE FROM A LIST

Here we look at the process of creating an unbalanced binary tree from a list of numbers.

We'll start with the list [5, 2, 7, 1, 4, 6, 8].

Here's the basic idea for creating an unbalanced binary tree: You start with the first number as the root of the tree. Then for each number, you traverse the tree, starting from the root, and place the number in the correct spot. If the number is smaller than the current node, you go left; if it's larger, you go right. You do this until you find an empty spot where you can place your number.

Here's the step-by-step breakdown:

1. Start with an empty tree. Our list of numbers is [5, 2, 7, 1, 4, 6, 8].
2. Take the first number, 5. Since the tree is empty, 5 becomes the root.
3. The next number is 2. 2 is less than 5, so it becomes the left child of 5.
4. The next number is 7. 7 is greater than 5, so it becomes the right child of 5.
5. The next number is 1. Starting at the root, we see that 1 is less than 5, so we go left. Then, 1 is less than 2, so it becomes the left child of 2.
6. The next number is 4. We start at the root. 4 is less than 5, so we go left. Then, 4 is greater than 2, so it becomes the right child of 2.
7. The next number is 6. Starting at the root, 6 is greater than 5, so we go right. Then, 6 is less than 7, so it becomes the left child of 7.
8. Finally, we insert the number 8. Starting at the root, 8 is greater than 5, so we go right. Then, 8 is greater than 7, so it becomes the right child of 7.

So, the final binary tree would look like this:

MARKDOWN | RESULT FROM CREATING UNBALANCED TREE FROM GIVEN LIST

As you can see, this tree is unbalanced. There are more nodes on the right side of the root node than on the left. Similarly, within the subtree rooted at the node 2, there are more nodes on the right side than on the left.

Note: While the above tree is an unbalanced binary tree, it is not a worst-case scenario. If we had inserted the numbers in a sorted order (either ascending or descending), we would have ended up with a degenerate tree, which would have been the most unbalanced possible tree.

​This video is a walk through of creating a tree from a given list. In this video the list is an un-sorted list and the Tree produced is a Un-balanced Binary Tree.

TREE TRAVERSAL

Traversal can be broken up into 2 categories; Depth First and Breadth First.
The depth-first methods are:
​Pre-Order: First Visit
In-Order: Second or last visit - whichever comes first
Post-Order: Last visit

The breath-first method is:
Level-order: Traverse the tree from top to bottom and visit left to right : like reading a book.

PRE-ORDER TRAVERSAL

Pre-order traversal is commonly used in algorithms where the operation at a node should be performed before the operations at its children, like when creating a copy of a tree.

1: Visit Node
2: Traverse Left
​3: If Null Traverse Right

PRE-ORDER TRAVERSAL: 1, 2, 4, 5, 3, 7

IN-ORDER TRAVERSAL

In-order traversal is often used when you want to retrieve data from a binary search tree in ascending order.

We can think of In-order traversal as visiting the node on the second visit. A leaf nodes second visit would be after checking the null value of branches, so it may be actually be the first visit however we can still view it as the second visit as it traverses the null value.
1: Traverse Left
2: Visit Node
​3: Traverse Right

IN-ORDER TRAVERSAL: 4, 2, 5, 1, 3, 7

POST-ORDER TRAVERSAL

Post order traversal is typically used when the operation at a node depends on the results of the operations at its children, like when deleting a tree.

If we assign a West and East side to the node, then the traversal must reach both the West and East points of the node before visiting. Traversing the north or south of a node does not count as a pass.
1: Traverse Left
2: Traverse Right
​3: Visit Node

POST-ORDER TRAVERSAL: 4, 5, 2, 7, 3, 1

1. What is a tree data structure and how does it differ from a linked list data structure?
2. What is the root node in a tree and what is its purpose?
3. What are the different parts of a tree and what are their roles?
4. What is an in-order traversal and when is it used in tree algorithms?
5. What is a pre-order traversal and when is it used in tree algorithms?
6. What is a post-order traversal and when is it used in tree algorithms?
7. What is a binary tree and how does it differ from a general tree?
8. What is a balanced tree and what is its purpose?
9. How can you implement a binary search tree and what are its properties?
10. What is a Heap data structure and how does it differ from a binary search tree?
11. Given the following list of numbers: [12, 6, 20, 3, 10, 16, 25, 2, 5, 15]
    

​Construct an unbalanced binary search tree by inserting the numbers into the tree in the order they appear in the list.

OTHER GOOD RESOURCES FOR THIS SECTION

INTERVIEW BIT  A great selection of learning resources and multiple programming language examples.