Data Structures - Binary Tree

<< Previous

Next >>





It is a tree in which each node can have at most two children.


Figure 1 - Binary Tree

  • It consist of a root, two subtree TL and TR, possibly both of which could be empty.
  • It is necessary to determine whether the tree is balanced by calculating the balance factor.
  • The balance factor is defined as the difference in height between its left and right subtrees.

    B = HL - HR

  • The tree is balanced only if its balance factor is zero and its subtrees are also balanced.

Complete Binary Tree

A tree is considered complete tree if it has maximum number of entries for its height.

Figure 2 - Example of Complete Binary Tree

Nearly Complete Binary Tree

A tree is considered nearly complete tree if it has minimum number of entries for its height.

Figure 3 - Example of Nearly Complete Binary Tree

All the nodes in the last level are found on the left.

Binary Tree Traversal

Traversal is the process of visiting all the nodes in the tree exactly once. We have several approaches to traverse the tree that can be categorized into two approaches:

  • Depth First Traversal
  • Breadth First Traversal

Depth First Traversal


Figure 4 - Example Tree

All the descendants of a child are processed before next child.
There are 3 types of depth first traversal:

  • In-Order Traversal: first visit left child; then root and then right child (Left-Root-Right)
  • Pre-Order Traversal: first visit root; then left and right children. (Root-Left-Right)
  • Post-Order Traversal: first visit left child and right child;then root. (Left-Right-Root)
    As in example tree:
  • In-Order Traversal:
           3-5-7-3-2-4-1-6
  • Pre-Order Traversal:
           3-5-3-7-4-2-6-1
  • Post-Order Traversal:
           3-7-5-2-1-6-4-3

Breadth First Traversal

  • The processing start horizontally from the root to all its children, then to its children's children and so forth until all nodes have been processed.
  • That means, each level is completely processed before the next level is started.
    Let as consider the same example tree (Figure 4) the breadth first traversal is:
    3-5-4-3-7-2-6-1

<< Previous

Next >>




Learn Djikstra's Algorithm

Krivalar.com © 2017