# Binary Trees

# Binary Trees¶

This article introduces the basic concepts of binary trees, and then works through a series of practice problems with solution code in Python. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.

## Introduction To Binary Trees¶

A binary tree is made of nodes, where each node contains a**left**pointer, a

**right**pointer, and a data element. The

**root**pointer points to the topmost node in the tree.

(source: Leaf it up to binary trees )

The left and right pointers recursively point to smaller **subtrees** on either side. A null pointer represents a binary tree with no elements--**the empty tree**.

The formal recursive definition is: a tree is called **binary tree** if each node has **zero child**, **one child**, or **two childern**.

## Types of Binary Trees¶

**Strict Binary Tree:**each node has**exactly two children or no children**.

**Full Binary Tree:**each node has**exactly two children**and**all leaf nodes are at the same level**.

**Complete Binary Tree:**every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

## Structure of Binary Trees¶

Now let us define the structure of a binary tree. One way to represent a node (which contains data) is to have two links which points to left and right children along with data fields. In Python, the binary tree is built with a node type like this ...

```
# Binary Tree node class
class BinaryTreeNode:
def __init__(self, data, left=None, right=None):
"""defines a BT node with data, left child, and right child pointers"""
self.data = data
self.left = left
self.right = right
```

Now let us define the actual binary tree. We will create a new class and initialize it with the root node

```
# Binary Tree class
class BinaryTree:
def __init__(self, root=None):
self.root = root
```

In the next paragraph, we will create the following binary tree

```
# create a binary tree and set 10 as root node
BT = BinaryTree(BinaryTreeNode(10))
# Add child nodes 9, 7 to root node
BT.root.left = BinaryTreeNode(9)
BT.root.right = BinaryTreeNode(7)
# Add child nodes 8, 6 to node 9
BT.root.left.left = BinaryTreeNode(8)
BT.root.left.right = BinaryTreeNode(6)
# Add child nodes 2, 4 to node 7
BT.root.right.left = BinaryTreeNode(2)
BT.root.right.right = BinaryTreeNode(4)
```

```
BT.root.data, BT.root.left.data, BT.root.right.data
```

## Binary Tree Traversals¶

The process of visiting all nodes of a tree is called **tree traversal**. Each node is processed only once but it may be visited more than once.

There are **three main traversal methods**:

**Preorder (current node (D) -> Left node (L) -> Right node (R))**Traversal**Inorder (Left node (L) -> current node (D) -> Right node (R))**Traversal**Postorder (Left node (L) -> Right node (R) -> current node (D))**Traversal

There is another traversal method which does not depend on the above orders and it is:

**Level Order**Traversal: This method is inspired from*Breadth First Search*

(source: https://en.wikipedia.org/wiki/Breadth-first_search)

### PreOrder Traversal¶

- Each node is processed before either of its subtrees.
- Even though each node is processed before the subtrees, this method still requires that some information must be maintained while moving down the tree.
- Therefore, processing must return to the right subtree after finishing the processing of the left subtree. To move to the right subtree after processing the left subtree, we must maintain the root information. The suitable data structure for such task is
**a stack**.

Preorder traversal is defined as follows:

- Visit the root.
- Traverse the left subtree in Preorder
- Traverse the right subtree in Preorder

```
def preorder_traversal_recursive(root):
"""Function performs preorder traversal recursively. The nodes are printed
in traversal order."""
if root is None:
return
print(root.data, end=' ')
preorder_traversal_recursive(root.left)
preorder_traversal_recursive(root.right)
```

```
preorder_traversal_recursive(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

For an iterative solution, in order to simulate a stack, we use Python's list data structure. The `push()`

method will be simulated by `append()`

and the `pop()`

method will be simulate by `pop()`

.

```
def preorder_traversal_iterative(root):
"""Function performs preorder traversal iteratively."""
if root is None:
return
stack = []
stack.append(root)
while stack:
current = stack.pop()
print(current.data, end=' ')
if current.right is not None:
stack.append(current.right)
if current.left is not None:
stack.append(current.left)
```

```
preorder_traversal_iterative(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### InOrder Traversal¶

In InOrder traversal, the root is visited between the subtrees. InOrder traversal is defined as follows:

- Traverse the left subtree in Inorder
- Visit the root
- Traverse the right subtree in InOrder

```
def inorder_traversal_recursive(root):
"""Function performs inorder traversal recursively. The nodes are printed
in traversal order."""
if root is None:
return
inorder_traversal_recursive(root.left)
print(root.data, end=' ')
inorder_traversal_recursive(root.right)
```

```
inorder_traversal_recursive(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### PostOrder Traversal¶

In PostOrder traversal, the root is visited after both subtrees. PostOrder traversal is defined as follows:

- Traverse the left subtree in Postorder
- Traverse the right subtree in PostOrder
- Visit the root

```
def postorder_traversal_recursive(root):
"""Function performs postorder traversal recursively. The nodes are printed
in traversal order."""
if root is None:
return
postorder_traversal_recursive(root.left)
postorder_traversal_recursive(root.right)
print(root.data, end=' ')
```

```
postorder_traversal_recursive(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### Level Order Traversal¶

Level Order Traversal is defined as follows:

- Visit the root
- While traversing level $l$, keep all the elements at level $l+1$ in queue.
- Go to the next level and visit all the nodes at that level.
- Repeat this until all levels are completed

```
import queue
def level_order(root):
if root is None:
return
q = queue.Queue()
q.put(root)
while not q.empty():
current = q.get()
print(current.data, end=' ')
if current.left is not None:
q.put(current.left)
if current.right is not None:
q.put(current.right)
```

```
level_order(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

## Binary Tree Problems¶

Here are 4 binary tree problems with their Python implementations. Reading about a data structure is a fine introduction, but at some point the only way to learn is to actually try to solve some problems starting with a blank sheet of paper. To get the most out of these problems, **you should at least attempt to solve them before looking at the solution**. Even if your solution is not quite right, you will be building up the right skills. With any pointer-based code, it's a good idea to make memory drawings of a a few simple cases to see how the algorithm should work.

The following problems will use the following tree as an example:

### Problem-1: Give algorithms for finding maximum and minimum element in a binary tree¶

**Solution-1:**

- Find the maximum/minimum element in left subtree
- Find the maximum/minimum element in right subtree
- Compare them with the root data and select the one which is giving the maximum/minimum value.

```
def find_maximum(root):
"""finds and returns maximum element in a binary tree"""
maximum = float("-infinity")
if root is None:
return maximum
res = root.data
lres = find_maximum(root.left)
rres = find_maximum(root.right)
return max(max(lres, rres), res)
```

```
print(find_maximum(BT.root))
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

```
def find_minimum(root):
"""finds and returns minimum element in a binary tree"""
#global minimum
minimum = float("infinity")
if root is None:
return minimum
res = root.data
lres = find_minimum(root.left)
rres = find_minimum(root.right)
return min(min(lres, rres), res)
```

```
find_minimum(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

**Solution-2:**

- Using level order traversal: observe the current node's data while removing the element from the queue.

```
import queue
def find_max_level_order(root):
if root is None:
return
q = queue.Queue()
q.put(root)
maximum = float("-infinity")
while not q.empty():
current = q.get()
maximum = max(maximum, current.data)
if current.left is not None:
q.put(current.left)
if current.right is not None:
q.put(current.right)
return maximum
```

```
find_max_level_order(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### Problem-2: Searching an element in a binary Tree¶

**Solution-1:**

- Return 1 if a node with data is found in the tree.
- Recurse down the tree, choose left or right by comparing data with each node's data
- Return -1 if not found

```
def find_element(root, data):
if root is None:
return -1
if root.data == data:
return 1
else:
temp = find_element(root.left, data)
if temp == 1: # if the element is found
return temp
else: # Search in the right subtree
return find_element(root.right, data)
```

```
find_element(BT.root, 14)
```

```
find_element(BT.root, 2)
```

**Solution-2:**

- Use level order traversal for solving this problem.
- The only change required in level order traversal is, checking whether the current node data is equal to the element we are looking for.

```
def find_element_level_order(root, data):
"""Function that search for an element in a given binary tree.
Returns 1 if the element is found, and -1 if not found."""
if root is None:
return
q = queue.Queue()
q.put(root)
while not q.empty():
current = q.get()
if current.data == data:
return 1
else:
if current.left is not None:
q.put(current.left)
if current.right is not None:
q.put(current.right)
return -1 # if not found
```

```
find_element_level_order(BT.root, 14)
```

```
find_element_level_order(BT.root, 2)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### Problem-3: finding the size of a binary tree¶

**Solution-1:**

- Calculate the size of left and right subtrees recursively
- Add 1 (current node) and return to its parent

```
def find_size(root):
"""Function to find the size of a binary tree """
if root is None:
return 0
return find_size(root.left) + find_size(root.right) + 1
```

```
find_size(BT.root)
```

**Solution-2:**

- Use level order traversal

```
def find_size_using_level_order(root):
if root is None:
return 0
q = queue.Queue()
q.put(root)
counter = 0
while not q.empty():
current = q.get()
counter += 1
if current.left is not None:
q.put(current.left)
if current.right is not None:
q.put(current.right)
return counter
```

```
find_size_using_level_order(BT.root)
```

**Time Complexity: $O(n)$****Space Complexity: $O(n)$**

### Problem-4: Print the level order data in reverse order¶

**Solution:**

- Use a stack to simulate Last In First Out (LIFO) in addition to the queue for level order traversal

```
def reverse_level_order_traversal(root):
"""Function for printing the level order data in reverse order"""
if root is None:
return
q = queue.Queue()
stack = []
q.put(root)
while not q.empty():
current = q.get()
stack.append(current)
if current.left is not None:
q.put(current.left)
if current.right is not None:
q.put(current.right)
while stack:
print(stack.pop().data, end=' ')
```

```
level_order(BT.root)
```

```
reverse_level_order_traversal(BT.root)
```