simplebooklet thumbnail

of 0
Tree IIITS
Nature View of a Tree leaves  branches root
Computer Scientist   s View root leaves  branches nodes
What is a Tree  A tree is a finite nonempty set of elements. It is an abstract model of a hierarchical structure. consists...
Syntax Tree for aSentence I ate the cake S subject  NP I verb  VP V ate  NP Det the  N cake object
Syntax tree for anExpression 2 sin 3z     7     2  sin         3  7 z
Geography Hierarchy Jackson  Wyoming United States         Alabama  World         United Kingdom  Cheyenne Montgomery  Wal...
Animal Kingdom Arachnid  Animal  Invertebrate           Butterflies  Reptile  Insect  Flies Beetles  Amphibian Bird  Roden...
Abstract Syntax Tree for Code while x   0  x   x  2 foo x  while compare op    var  x  block  const  0  assign  var  x  pr...
Definition     A recursive definition ATree is  empty, or a node with  a key, and a list of child trees.
Simple Tree Empty tree  Tree with one node  Fred Tree with two nodes  Fred Sally
Terminology Fred Kate Sam  Sally  Hugh  Jim
Terminology Fred Kate Sam  Sally  Jim  Hugh  Root  top node in the tree
Terminology Fred Kate Sam  Sally  Jim  Hugh  A child has a line down directly from a parent
Terminology Fred Kate Sam  Sally  Jim  Hugh  Kate is a parent of Sam
Terminology Fred Kate Sam  Sally  Jim  Hugh  Sam is a child of Kate
Terminology Fred Kate Sam  Sally  Jim  Hugh  Ancestor  parent, or parent of parent, etc.
Terminology Fred Kate Sam  Sally  Jim  Hugh  Ancestors of Sam
Terminology Fred Kate Sam  Sally  Jim  Hugh  Descendant  child, or child of child, etc.
Terminology Fred Kate Sam  Sally  Jim  Hugh  Descendants of Fred
Terminology Fred Kate Sam  Sally  Jim  Hugh  Sibling   sharing the same parent
Terminology Fred Kate Sam  Sally  Jim  Hugh  Leaf   node with no children
Terminology Fred Kate Sam  Sally  Jim  Hugh Interior node  non-leaf
Terminology Fred Kate Sam  Sally  Hugh Level 1  Jim
Terminology Fred Kate Sam  Sally  Hugh Level 2  Jim
Terminology Fred Kate Sam  Sally  Hugh Level 3  Jim
Terminology Fred Kate Sam  Sally  Jim  Hugh  Height  maximum depth of subtree node and farthest leaf
Terminology Fred Kate Sam  Sally  Hugh Height 1  Jim
Terminology Fred Kate Sam  Sally  Hugh Height 2  Jim
Terminology Fred Kate Sam  Sally  Hugh Height 3  Jim
Terminology Fred Kate Sam  Sally  Jim  Hugh  Height of the tree is 3
Height tree  if tree   nil  return 0 return 1   Max Height tree.left , Height tree.right
Size tree  if tree   nil return 0 return 1   Size tree.left    Size tree.right
Terminology Kate Sam  Hugh  Sally Jim  Forest  collection of trees
Tree Terminologies - Summary v Root  node without parent  A  v Siblings  nodes share the same parent v Internal node  node...
Binary Tree For binary tree, nodecontains  key left right  optional  parent
Complete Binary Tree A complete binary tree is a binary tree in which every level, except possibly the last, is completely...
Trees - ADT Every tree node  object     useful information or data children     pointers to its children  Data  Data  F  D...
A Tree Representation A node is represented by an object storing  Element Parent node Sequence of children nodes      B   ...
Assignment
Assignment
Walking a Tree Often we want to visit the nodes of a tree in a particular order. For example, print the nodes of the tree....
Walking a Tree Often we want to visit the nodes of a tree in a particular order. For example, print the nodesof the tree. ...
Walking a Tree Often we want to visit the nodes of a tree in a particular order. For example, print the nodesof the tree. ...
Depth-first InOrderTraversal tree  if tree   nil  return InOrderTraversal tree.left  Print tree.key   InOrderTraversal tre...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Cathy  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Cathy  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  AlexCathy  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Output  Alex Cathy Frank  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Cathy Frank  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Cathy Frank  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Cathy Frank  Wendy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy FrankLes
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy FrankLes
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy FrankLes
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy FrankLes
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
InOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Cathy Frank Les Nancy Sam Tony Violet...
Assignment          Take input from user in InOrder and create the binary tree. Draw the Tree
Depth-first PreOrderTraversal tree  if tree   nil  return Print tree.key   PreOrderTraversal tree.left  PreOrderTraversal ...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  LesCathy  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy Alex  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy Alex  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy Alex  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Les Cathy Alex  Wendy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex FrankSam
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex FrankSam
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex FrankSam
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
PreOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Alex Frank Sam Nancy Violet Ton...
Depth-first PostOrderTraversal tree  if tree   nil  return PostOrderTraversal tree.left  PostOrderTraversal tree.right  Pr...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output   Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  AlexFrank  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank Cathy  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank Cathy  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank Cathy  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank Cathy  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony Output  Alex Frank Cathy  Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
PostOrderTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Alex Frank Cathy Nancy Tony Wendy Violet...
Construct a Tree Inorder sequence  D B E A F C  Can we construct a tree  Which one is the root node
Construct a Tree Inorder sequence  D B E A F C Preorder sequence  A B D E C F      In a Preorder sequence, leftmost elemen...
Construct a Tree Inorder sequence  D B E A F C Preorder sequence  A B D E C F
Construct a Tree Inorder sequence  D B E A F C Preorder sequence  A B D E C F
Construct a Tree Inorder sequence  D B E A F C Preorder sequence  A B D E C F  Algorithm  buildTree   1. First element in ...
Construct a Tree  Inorder sequence  D B E A F C Preorder sequence  A B D E C F
Construct a Tree  Inorder sequence  D B E A F C Preorder sequence  A B D E C F
Assignment              Can you do it for InOrder and PostOrder  Validity check - InOrder and PreOrder are given, but tree...
LevelTraversal Les Cathy Alex  Frank  Sam Nancy  Violet  Tony  Wendy  Output  Les Cathy Sam Alex FrankNancy Violet Tony We...
Assignment                  Can you do it for InOrder and PostOrder  Validity check - InOrder and PreOrder are given, but ...
Binary Search Tree Binary Search tree property  all keys in left subtree smaller than root   s key all keys in right subtr...
Complete Binary Search Tree Complete binary search tree  Links are completely filled, except possibly bottom level, which ...
In-Order Traversal 10 5  What does this guarantee with a BST  15  2  9 7  20 17 30  In order listing  2  5  7  9  10  15  ...
Recursive Find 10 5  15  2  9 7  20 17 30  Node   find Comparable key, Node   t    if  t    NULL  return t  else if  key  ...
Iterative Find 10 5  15  2  9 7  20 17 30  Node   find Comparable key, Node   t    while  t    NULL    t- key    key    if...
Assignment                           Can you do it for InOrder and PostOrder  Validity check - InOrder and PreOrder are gi...