Binary Trees

Question 1

Binary tree are both

Answer 1

1) Recursive

2) Ordered

Question 2

Depth three items

Answer 2

1) inoreder
2) perorder
3) Postorder

Question 3

Killer feature

Answer 3

Searching

Question 4

Killer feature

Answer 4

Searching - 1/2 ‘s the search each pass

Question 5

Binary Tree - How is data stored

Answer 5

Nodes (like leafs on a tree)

Question 6

Binary Tree - How is data stored

Answer 6

Nodes (like leafs on a tree) with keys

Question 7

Binary tree - Describe a full binary tree

Answer 7

Tree with zero or two children (no single children)

Question 8

Binary tree - Describe a balanced binary tree

Answer 8

It has the minimum possible height

Question 9

Binary tree - Breadth first

Answer 9

Search across the tree first (think the data is somewhere near the top)

Question 10

What type of algorithms use Breadth first

Answer 10

shortest pass

Question 11

Binary tree - depth First

Answer 11

Think the data is deep deep down the tree

example: maze problems

Question 12

Binary Search Tree (BST) - how are nodes(keys) sorted

Answer 12

Nodes keys are sorted top to Bottom
all the nodes left of the parent are smaller then the parent, And all the nodes right to the parent are larger
                      5
                     /  \
                  3       7
                 / \      /  \
               2  4     6 8

Also every level search eliminates half of the data

Question 13

Binary Search Tree (BST) search find 4 (how many hops)

                      5
                     /  \
                  3       7
                 / \      /  \
               2  4     6 8

Answer 13

5  4<> ?
                     /  \
   4<> ?      3       7
                 / \      /  \
               2  4     6 8

three hops

Question 14

Binary insert - How to insert a (2)

      5
    /
 3

Answer 14

1) start at 5 (it is less than 5 so it goes on the left
2) Is it great then or less then 3 (it is less then so we go down)
3) so Insert it to the empty node below 3

          5
        /
     3
  /
2

Question 15

Binary insert - How to insert a (4)

      5
    /
 3

Answer 15

5
        /  
     3 
   /    \
 2       4     

Four is greater then three so go to right node

Question 16

Binary insert - How to insert a (7)

          5
        /  
     3 
   /    \
 2       4

Answer 16

7 is greater then 5 so branch to right

          5
        /   \
     3       7
   /    \
 2       4

Question 17

How to find the minimum in a binary Search Tree

Answer 17

easy (just go down the left side to get the minimum key value (smallest numbers are always on the left side)
                      5
                     /  \
                  3       7
                 / \      /  \
               2  4     6 8
              /
            null

Question 18

delete from a binary Search Tree (what are the cases)

Answer 18

1) No Child
2) One Child
3) Two children

Question 19

delete from a binary Search Tree - No Child

Answer 19

Just find it and set it to null

Question 20

delete from a binary Search Tree - One Child

Answer 20

Replace the node that being deleted with the child

Question 21

delete from a binary Search Tree - Two children

Answer 21

Most complex - convert tree to one that our node only has one child

1) find minimum on the correct side that will fit into the position
2) replace that node with the new node
3) delete the original new node

Question 22

delete from a binary Search Tree - Two children (delete 5)
5
/ \
2 3

Answer 22

1) Go down the right side
2) find minimum value
3) Copy it to the position of the 5
4) remove duplicate

Question 23

Depth first traversal - Inorder

Answer 23

Left first, Root, Right)
Start on Left, goto Root, Right
2,1,3
         1
        /   \
     2       3

order = root midle

Question 24

Why use Depth first traversal - Inorder

Answer 24

Good if inherent order in tree

example: print out all the elements in the tree

Question 25

Depth first traversal - Preorder

Answer 25

Start at top Left and then Right
1,2,3
         1
        /   \
     2       3

Pre = root first

Question 26

Why use Depth first traversal - Preorder

Answer 26

Good for Copying and Expression trees

Question 27

Depth first traversal - Postorder

Answer 27

Root goes last (bottom up,used in Delete )
Left,Right, Root
2,3,1
         1
        /   \
     2       3

Post = root last

Question 28

Run-time Binary Search Tree B-O number

find, insert, delete

Answer 28

O(log n)

Every time the binary tree recuses it halves the search group

1/2 1/4 1/8 1/16 …