FREE C PROGRAMS

Data Structures and C Programming

  DATA STRUCTURES USING C

 HOME PAGE

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 non-linear 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
  • Non-root and non-leaf 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 height-balanced 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

-----------------------------------