Binary Trees¶
A tree is a type of linked data structure of nodes. Every node has multiple pointers that point to other nodes (or nullptr). The whole structure is pointed to with a root pointer, which points to the root node. If a node points to another, the node it points to is the child node and the node itself is the parent node. If a tree doesn’t have any nodes, it is called an empty tree. If node doesn’t have any children (it doesn’t point to anything), it is called a leaf node.
A binary tree is a type of tree in which every node has at most two children nodes (left and right pointer).
Two nodes that descend form the same parent node are called sibling nodes.
A sub-tree is a term that can be used to describe any node that isn’t the root node.
The node depth is how many levels of siblings a certain node is from the root node.
The root node has a depth of 0, it’s children have a depth of 1, etc.
A full binary tree is a binary tree in which every non-leaf node has two children, and every leaf node has the same depth.
Traversals¶
There are four different ways to traverse the nodes of a binary tree (to visit every node of a tree): - pre-order, - in-order, - post-order, and - level-order.
PRE-ORDER¶
- Do something with the current node (it could be to print it out, change the value, etc.)
- Go to the nodes in the left sub-tree and repeat process
- Go to the nodes in the right sub-tree and repeat process
Code:
void preorder(Node *cur)
{
if (cur == nullptr) // If the tree is an empty tree
return;
cout << cur->value; // In this case we print out the value
preorder(cur->left); // Recursively do the same to the left and right sub-trees
preorder(cur->right);
}
a
b c
d e
Example:
Current root is a
Print out a
Go to left sub-tree
Print out b
Go to left sub-tree
Print out d
Go to left sub-tree
Return (no child)
Go to right sub-tree
Return
Go to right sub-tree
Print out b
Go to left sub-tree
Return
Go to right sub-tree
Return
Go to right sub-tree
Print out c
Go to left sub-tree
Return
Go to right sub-tree
Return
Output:
a b d e c
How to visualize it: Go down every line of nodes diagonally, top to bottom
IN-ORDER¶
- Go to the nodes in the left sub-tree
- Do something with the current node
- Go to the nodes in the right sub-tree
Notice that in this order we first go all the way to the left before printing anything out (this includes the root node)
Code:
void inorder(Node *cur)
{
if (cur == nullptr)
return;
inorder(cur->left);
cout << cur->value;
inorder(cur->right);
}
a
b c
d e
Example:
Current root is a
Go to left sub-tree (b)
Go to left sub-tree (d)
Go to left sub-tree (null)
Return
Print out d
Go to right sub-tree (null)
Return
Print out b
Go to right sub-tree(e)
Go to left sub-tree (null)
Return
Print out e
Go to right sub-tree (null)
Return
Print out a
Go to right sub-tree (c)
Go to left sub-tree (null)
Return
Print out c
Go to right sub-tree (null)
Return
Output:
d b e a c
How to visualize it: start at the left side of tree, go vertically right, bottom to top
POST-ORDER¶
- Go to the nodes in the left sub-tree
- Go to the nodes in the right sub-tree
- Do something with the current node
Code:
void postorder(Node *cur)
{
if (cur == nullptr)
return;
postorder(cur->left);
postorder(cur->right);
cout << cur->value;
}
a
b c
d e
Example:
Current root is a
Go to the left sub-tree (b)
Go to the left sub-tree (d)
Go to the left sub-tree (null)
Return
Go to the right sub-tree (null)
Return
Print out d
Go to the right sub-tree(e)
Go to the left sub-tree (null)
Return
Go to the right sub-tree (null)
Return
Print out e
Print out b
Go to the right sub-tree (c)
Go to the left sub-tree (null)
Return
Go to the right sub-tree (null)
Return
Print out c
Print out a
Output:
d e b c a
How to visualize it: start at the bottom of the tree, go horizontally up, left to right
LEVEL-ORDER¶
- Use a pointer variable and a queue of pointers to nodes
- Push the root node pointer onto the queue
- While the queue is not empty,
- Pop the top node
- Do something to the node
- Push the node’s children to the queue
Code:
void levelorder(Node *cur)
{
if (cur == nullptr)
return;
Node *temp;
queue<Node*> toProcess;
toProcess.push_back(cur);
while (!toProcess.empty())
{
temp = toProcess.front();
toProcess.pop();
cout << temp->value;
if (temp->left != nullptr)
toProcess.push_back(temp->left);
if (temp->right != nullptr)
toProcess.push_back(temp->right);
}
}
a
b c
d e
Example:
Current root is a
Push a
QUEUE: a
Pop a, print out a
QUEUE:
Push b
Push c
QUEUE: b c
Pop b, print out b
QUEUE: c
Push d
Push e
QUEUE: c d e
Pop c, print out c
QUEUE: d e
Don't push anything
Pop d, print out d
QUEUE: e
Don't push anything
Pop e, print out e
Don't push anything
Done!
Output:
a b c d e
How to visualize: Start from the top of the tree, go down horizontally, left to right
The big-O of all of these traversals is O(N).
You can also evaluate expressions with a binary tree.
For example, 2 + 3 would be represented with this tree:
+
2 3
Here is the algorithm to evaluate it: 1. If the current node’s value is a number, return its value 2. Recursively evaluate the left sub-tree and get the result 3. Recursively evaluate the right sub-tree and get the result 4. Apply the operator in the current node to the left and right results; return the result.
(5 + 6) * (3 - 1):
*
+ -
5 6 3 1
Example:
Current node is *
Go to the left sub-tree
Current node is +
Go to left sub-tree
Current node is 5
Return 5
Go to right sub-tree
Current node is 6
Return 6
Apply + to 5 and 6
Return 11
Go to right sub-tree
Current node is -
Go to left sub-tree
Current node is 3
Return 3
Go to right sub-tree
Current node is 1
Return 1
Apply - to 3 and 1
Return 2
Apply * to 11 and 2
Return 22