Data Structures Interview Questions
Pg : 1 , 2,
3, 4,
5, 6,
7, 8,
9, 10,
11, 12,
13, 14
Trees
Definition of Tree
A tree is basically a finite set of one or more nodes
such that:
 There is a specially designated node called
the root.
 The remaining nodes are partitioned into n>=0
disjoint sets T1, ., Tn, where each of these sets is a tree.
 We call T1, ., Tn the subtrees of the root
 A tree is a nonlinear data structure that
consists of a root node and potentially many levels of additional
nodes that form a hierarchy
 Nodes that have no children are called leaf
nodes
 Nonroot and nonleaf nodes are called
internal nodes
A Binary Search Tree is a binary tree with the following properties:
 All items in the left subtree are less than
the root.
 All items in the right subtree are greater or
equal to the root.
 Each subtree is itself a binary search tree.
AVL  Good but not Perfect Balance
 AVL trees are heightbalanced binary search
trees
 Balance factor of a node
 height(left subtree)  height(right
subtree)
 An AVL tree has balance factor calculated at
every node
 For every node, heights of left and right
subtree can differ by no more than 1
 Store current heights in each node


