Binary Trees

Advantages of trees

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

  • Trees reflect structural relationships in the data
  • Trees are used to represent hierarchies
  • Trees provide an efficient insertion and searching
  • Trees are very flexible data, allowing to move sub-trees around with minimum effort

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

  • depth-first traversal
  • breadth-first traversal
  • PreOrder traversal — visit the parent first and then left and right children;
  • InOrder traversal — visit the left child, then the parent and the right child;
  • PostOrder traversal — visit left child, then the right child and then the parent;

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
  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.
  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.

  • Full binary tree: Every node other than leaf nodes has 2 child nodes.
  • Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
  • Perfect binary tree: All nodes have two children and all leaves are at the same level.

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.

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.
  • Searching: For searching element 1, we have to traverse all elements (in order 3, 2, 1). Therefore, searching in binary search tree has worst case complexity of O(n). In general, time complexity is O(h) where h is height of BST.
  • Insertion: For inserting element 0, it must be inserted as left child of 1. Therefore, we need to traverse all elements (in order 3, 2, 1) to insert 0 which has worst case complexity of O(n). In general, time complexity is O(h).
  • Deletion: For deletion of element 1, we have to traverse all elements to find 1 (in order 3, 2, 1). Therefore, deletion in binary tree has worst case complexity of O(n). In general, time complexity is O(h).

AVL Tree

  • AVL tree is a height balanced tree.
  • It is a self-balancing binary search tree.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store