Binary Tree

Terminology

• Node:

  • The most elementary unit of binary tree

  • Every node has three parts (LinkedList representation of binary tree):

    • data for the node

    • pointer to the left child

    • pointer to right child

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

• Parent node: The parent is that node which is one level up the current node

• Child node: The children of a node are the nodes that are one level downward of the node

• Root node:

  • root is the topmost element in the binary tree

  • there is only one root, it is like the one we had as head in Singly LinkedList

  • root node has no parent node

• Leaf node:

  • The nodes which have no child nodes are the leaf nodes in binary tree

  • leaf node has no child node

• Depth of a node:

  • The depth of different nodes is defined as the number of nodes that exist on the way that connects the root to a particular node.

  • That is why the depth of the root node is 0

  • The depth of a node is measured by starting from the root node and then going down to reach that node

• Height of a node:

  • the height of different nodes in a binary tree is the number of nodes that lie in the path that connects a particular node with the root node

  • That is why the height of leaf nodes is 0

  • When it comes to calculating the height, we start at the node in question and then journey towards the root node

Properties of Binary Tree

• Tree is a non-linear data structure

• Used for searching and data organisation

• Every node can have maximum of two children node (left child and right child)

• Binary tree does not allow duplicate values (in some cases, duplicate values are considered)

• While constructing a binary, if an element is less than the value of its parent node, it is placed on the left side of it otherwise right side

Types of Binary Tree

• Complete / Ideal Binary Tree

• Full / Strictly Binary Tree

• Extended Binary Tree

• Almost Complete Binary Tree

• Rooted Binary Tree

• Skewed Binary Tree

Operations in Binary Tree

insertion

deletion

searching

height of binary tree

traversal

Traversing a Tree

Depth First Traversal

• Inorder traversal:

  • Traverse the left sub tree i.e. call Inorder (left sub tree)

  • Visit the root

  • Traverse the right sub tree i.e. call Inorder (right sub tree)

Left → Root → Right

def inorder_traversal(self, node):
    if node is not None:
        inorder_traversal(node.left)
        print(root.data, end=' ')
        inorder_traversal(node.right)
        return

Inorder Traversal Example

• Postorder traversal:

  • Traverse the left sub tree i.e. call Postorder (left sub tree)

  • Traverse the right sub tree i.e. call Postorder (right sub tree)

  • Visit the root

  Left → Right → Root

def postorder_traversal(node):
    if node is not None:
        postorder_traversal(node.left)
        postorder_traversal(node.right )
        print(node.data, end=' ')
        return

Postorder Traversal Example

• Preorder traversal:

  • Visit the root

  • Traverse the left sub tree i.e. call Preorder (left sub tree)

  • Traverse the right sub tree i.e. call Preorder (right sub tree)

Root → Left → Right

def preorder_traversal(node):
    if node is not None:
        print(node.data, end=' ')
        preorder_traversal(node.left)
        preorder_traversal(node.right)
        return

Preorder Traversal Example

Breadth First Traversal

• Here, the objective is to traverse all the nodes at a particular level, before going to next level

• Recursion does not work in breadth first traversal

• Will use queue data structure for the purpose

def breadthFirstTrav(root):
    q = [] # solving using queue
    q.append(root)
    while len(q)>0:
        node = q.pop(0)
        print(node.data)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Implementation of Binary Tree

Practice Binary Tree

• Flatten Binary Tree to Linked List - LeetCode

• Sum Root to Leaf Numbers - LeetCode

• Symmetric Tree - LeetCode

• Binary Trees - Carnegie Mellon University

Advantages of Binary Tree:

1. Searching in Binary tree become faster.

2. Binary tree provides six traversals.

3. Two of six traversals give sorted order of elements.

4. Maximum and minimum elements can be directly picked up.

5. It is used for graph traversal and to convert an expression to postfix and prefix forms.

Use Cases of Binary Tree

• There are many other data structures that are derived from the idea of a binary tree, such as

  • binary search tree

  • syntax tree

  • heap

  • hash tree

  • red-black tree

  • binary trie

  • AVL tree

  • GGM tree

  • T-tree

  • Treap

References for Further Reading

https://en.wikipedia.org/wiki/Binary_tree

Binary Tree - javatpointwww.javatpoint.com

https://www.goeduhub.com/11261/what-are-properties-binary-tree-describe-various-operations

https://www.gatevidyalay.com/binary-tree-properties-important-formulas/

https://www.upgrad.com/blog/binary-tree-in-data-structure/