ch 4 trees

Question 1

depth

Answer 1

path from the root to n (root is at 0)

Question 2

height

Answer 2

leaf n to root (leaf is at 0)

Question 3

class Binarynode (what are the instance variables)

Answer 3

object element (the data in the node)
binarynode left (left child)
binarynode right (right child)

Question 4

how do we evaluate expression trees

Answer 4

push the values onto a stack until you come across an operand
then calculate the last two values, push it back onto the stack

Question 5

.contains

Answer 5

returns a boolean, is a recursive method
boolean contains(Anytype x, BinaryNode t)
if null, return false

int compareResult = x.compareTo(t.element)

if compareresult > 0
       return cotains (x, t.left);
if compareres8ult < 0
       return contains(x, t.right);
else
       return true //match

Question 6

findMin

Answer 6

recursive, just the very left most node

findMin(binarynode t)
if t == null
return null

else if t.left == null
return t.left

return findmin(t.left)

Question 7

insert

Answer 7

binarynode insert (anytype x, binarynode t)
if t == null
    return new binarynode (x, null, null)

int compareresult = x.compareto(t.element)

if compareresult < 0
    t.left = insert(x, t.left)
if compareresult > 0
    t.right = insert(x, t.right)
else
    do nothing // this means that the number already exists in the binary tree

return t;

Question 8

remove

Answer 8

if it has one child, just change the pointer from the target node to the child

if it has two children, the new parent is the smallest node of the right subtree
if(node.left !=null&& node.right !=null) {// two
childrennode.data = findMin(node.right).data;node.right =
remove(node.right, node.data);

Question 9

AVL Tree

Answer 9

tree with a balance condition

Question 10

single rotation

Answer 10

middle node becomes the parent, other two become the left or right children

Question 11

double rotation

Answer 11

zig zag zig etc

first swap the bottom two nodes so it turns into a scenario where it becomes a single rotation

Question 12

tree traversals

Answer 12

inorder, preorder, postorder
running time O(N)

printTree(binaryNode t)//inorder traversal
if t != null
    printTree(t.left)
    system.out.println(t.element);
    printtree(t.right)