Binary Heap properties

 A Binary Heap is a Binary Tree with following properties.

1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

• Arr[(i-1)/2]	Returns the parent node
  Arr[(2*i)+1]	Returns the left child node
  Arr[(2*i)+2]	Returns the right child node

Arr[(n/2) .... (n-1)] => will contain the leaf nodes, if n is the length of the array or total number of nodes.

The traversal method use to achieve Array representation is Level Order


Source: geeks for geeks

Powers of 2 to remember for scalability questions

 

O(log N)

O(N)

O(N log N)

O(N^2)

O(2^N)

O(N!)

Source: Cracking the coding interview

Binary Tree - DFS Preorder (Stacks)

See the Pen Binary Tree - DFS Preorder (Stacks) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS PostOrder (Recursion)

See the Pen DFS - Binary Tree PostOrder (Recursion) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS PreOrder (Recursive)

See the Pen Binary Tree DFS Pre-order traversal by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS Inorder Traversal (Recursion)

See the Pen DFS - Binary Tree Inorder (Recursion) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Tree BFS in JS (Queue/Array)

Tree properties

1. The maximum number of nodes at level ‘l’ of a binary tree is 2^l
2. The Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1, Height of a tree with a single node is considered as 1.

BFS Complexity
Time Complexity - O(n)
Space Complexity - O(n)

Notes: BFS slower than DFS

From geeksforgeeks: 

Extra space required for Level order traversal is likely to be more when tree is more balanced and extra space for Depth First Traversal is likely to be more when tree is less balanced.

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.

Exercise:
Which traversal should be used to print leaves of Binary Tree and why? DFS
Which traversal should be used to print nodes at k’th level where k is much less than total number of levels? BFS

See the Pen Tree BFS in JS (Recursive & Non-recursive Queue versions) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.