A binary tree is made of nodes, where each node contains a “left” reference, a “right” reference, and a data element. The topmost node in the tree is called the root.

Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds

There are three different types of depth-first traversals, :

BFS vs DFS for Binary Tree

BFS and DFSs of above TreeBreadth First Traversal : 1 2 3 4 5Depth First Traversals:
Preorder Traversal : 1 2 4 5 3
Inorder Traversal : 4 2 5 1 3
Postorder Traversal : 4 5 2 3 1

Is there any difference in terms of Time Complexity?
All four traversals require O(n) time as they visit every node exactly once.

Is there any difference in terms of Extra Space?
There is difference in terms of extra space required.

  1. Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.
  2. Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.

How to Pick One?

  1. Extra Space can be one factor (Explained above)
  2. Depth First Traversals are typically recursive and recursive code requires function call overheads.
  3. The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

Types of Binary Trees

There are 3 different types of binary trees which will be discussed in this lesson: 1) full, 2) complete and 3) perfect.

Binary Search Trees

We consider a particular kind of a binary tree called a Binary Search Tree (BST), sometimes called ordered or sorted binary trees. The basic idea behind this data structure is to have such a storing repository that provides the efficient way of data sorting, searching and retrieving.

On average, binary search trees with n nodes have O(log n)height. However, in the worst case, binary search trees can have O(n) height, when the unbalanced tree resembles a linked list (degenerate tree).

AVL Tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than 1 (one) for all nodes.

Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.