Sep-22-backup-notes.org

Lab 4 Notes

Next Prev Binary Tree

nextAncestor()

• returns the first ancestor that is next with respect to an inorder traversal or null if there is none
  • hint: use parent to go up in the binary tree

[Example 1]

• Consider node g in the following binary tree:

d, b, f, e, g, a, c
   ?     ?  ^  -

digraph BT {
  node[fontsize=20];
  d, b, f, e, g, a, c;
  g      [style="filled", fillcolor="green" ];  // myself
  e, b, a[style="filled", fillcolor="yellow"];  // my ancestors
  a -> b, c;
  b -> d, e;
  e -> f, g;
}

• What about node c?

next()

• returns the next node according to an inorder traversal

[Example 2]

• Consider node b in the following binary tree:

d, b, f, e, a, c
   ^  -

digraph BT {
  node[fontsize=20];
  d, b, f, e, g, a, c;
  g[style=invis];
  a -> b, c;
  b -> d, e;
  e -> f;
  e -> g[style=invis];
}

• What about e?

d, b, f, e, a, c
         ^  -