A brief summary of everything [Trees].
Trees:
Set of Nodes & Edges that connect them.
Between ANY TWO NODES THERE IS EXACTLY ONE PATH
PATH: connected sequence of EDGES.
Rooted Tree: One distinguished NODE is called a ROOT.
Every node C, except the ROOT has one parent P, the first node from the node C to the root is its parent P.
C is P's child
Root has No parent.
A node can have n children.
A tree has no loops.
LEAF: node with no children.
SIBLINGS: node with same parent.
ANCESTORS of node C: nodes in path from C to ROOT including C.
If node A is the ANCESTOR of node C then node C is a DESCENDANT of node A.
LENGTH of the PATH: Number of edges in the PATH.
DEPTH of node n: Length of path from node n to ROOT.
Depth of ROOT is 0.
HEIGHT of node n: Length of path from n to its deepest descendant.
Height of a leaf is 0.
Height of Root is HEIGHT OF TREE.
Traversals for a Tree:
Pre Order : Visit each Node before you visit its children. Eg: list the Directories in Tree form.
Post Order: Visit Node Children First before visiting the node itself: Eg Summing the size of Sub Folders.
In Order(Binary tree): Visit left child then the Node and then nodes right child.
Level Order(Breadth First): Visit root, then all Depth 1 node(left to right), then Depth 2 nodes, etc..
Depth First:Same as Pre Order.
A BINARY TREE:
A rooted tree where no node has more than 2 children.
Every child is either left child or the right child even if its the only child.
PERFECT BINARY TREE:
A B Tree where all nodes except the LEAF node have exactly two siblings.
A COMPLETE BINARY TREE:
A B Tree Where all the nodes are filled in the lower levels and the nodes in the Last level are kept to the almost LEFT as possible.
Common Interview Questions(B trees):
Q1)What are the number of NULL nodes a tree on N nodes.
A. The best way is to draw few trees and deduce the relation.
There are N nodes in the Binary Tree.
Each node except the ROOT has a parent, i.e N-1 Parents.
Each node can have 2 Siblings, i.e N nodes can have 2N siblings.
The total NULL nodes in a B tree of N nodes is 2N-(N-1), i.e N+1 Null nodes..
Q2) what is the minimum height of a B Tree with N nodes.
A. The height of a binary tree is minimum when its a Complete B-Tree.
At a given level there are 2^level elements
For a Complete B - Tree with height h the total number of elements is max((2^(N+1))-1).
(2 to the power of N+1 whole -1).
from the above two statement we can mathematically concolude the minimum height of a tree
with n elements is ceil(log2(N))-1 that is Ceiling the value of Log of N to base 2 whole -1.
Q3) What is the maximum height of a B Tree with N nodes.
A. The height is maximum when there is at most 1 node in a level. hence the answer is N-1.
Q4) Min and Max Leaf Nodes in a tree of N nodes.
A. Min leaf node is 1 (When there is at most one element in every level, the last level node is the only leaf)
Max leaf nodes is (N+1)/2
Q5) Number of leaf nodes in a complete binary tree of N nodes.
A. N is even N/2, and N is odd (N+1)/2, generalizing ceil(N/2).
Trees:
Set of Nodes & Edges that connect them.
Between ANY TWO NODES THERE IS EXACTLY ONE PATH
PATH: connected sequence of EDGES.
Rooted Tree: One distinguished NODE is called a ROOT.
Every node C, except the ROOT has one parent P, the first node from the node C to the root is its parent P.
C is P's child
Root has No parent.
A node can have n children.
A tree has no loops.
LEAF: node with no children.
SIBLINGS: node with same parent.
ANCESTORS of node C: nodes in path from C to ROOT including C.
If node A is the ANCESTOR of node C then node C is a DESCENDANT of node A.
LENGTH of the PATH: Number of edges in the PATH.
DEPTH of node n: Length of path from node n to ROOT.
Depth of ROOT is 0.
HEIGHT of node n: Length of path from n to its deepest descendant.
Height of a leaf is 0.
Height of Root is HEIGHT OF TREE.
Traversals for a Tree:
Pre Order : Visit each Node before you visit its children. Eg: list the Directories in Tree form.
Post Order: Visit Node Children First before visiting the node itself: Eg Summing the size of Sub Folders.
In Order(Binary tree): Visit left child then the Node and then nodes right child.
Level Order(Breadth First): Visit root, then all Depth 1 node(left to right), then Depth 2 nodes, etc..
Depth First:Same as Pre Order.
A BINARY TREE:
A rooted tree where no node has more than 2 children.
Every child is either left child or the right child even if its the only child.
PERFECT BINARY TREE:
A B Tree where all nodes except the LEAF node have exactly two siblings.
A COMPLETE BINARY TREE:
A B Tree Where all the nodes are filled in the lower levels and the nodes in the Last level are kept to the almost LEFT as possible.
Common Interview Questions(B trees):
Q1)What are the number of NULL nodes a tree on N nodes.
A. The best way is to draw few trees and deduce the relation.
There are N nodes in the Binary Tree.
Each node except the ROOT has a parent, i.e N-1 Parents.
Each node can have 2 Siblings, i.e N nodes can have 2N siblings.
The total NULL nodes in a B tree of N nodes is 2N-(N-1), i.e N+1 Null nodes..
Q2) what is the minimum height of a B Tree with N nodes.
A. The height of a binary tree is minimum when its a Complete B-Tree.
At a given level there are 2^level elements
For a Complete B - Tree with height h the total number of elements is max((2^(N+1))-1).
(2 to the power of N+1 whole -1).
from the above two statement we can mathematically concolude the minimum height of a tree
with n elements is ceil(log2(N))-1 that is Ceiling the value of Log of N to base 2 whole -1.
Q3) What is the maximum height of a B Tree with N nodes.
A. The height is maximum when there is at most 1 node in a level. hence the answer is N-1.
Q4) Min and Max Leaf Nodes in a tree of N nodes.
A. Min leaf node is 1 (When there is at most one element in every level, the last level node is the only leaf)
Max leaf nodes is (N+1)/2
Q5) Number of leaf nodes in a complete binary tree of N nodes.
A. N is even N/2, and N is odd (N+1)/2, generalizing ceil(N/2).
No comments:
Post a Comment