Binary Trees

Question 1

give the Tree ADT

Answer 1

e = element, v = node

root()
insert(e)
remove(v)
find(e)
parent(v)
children(v)
elements()
isExternal(v)

Question 2

describe the binary Tree ADT

Answer 2

at most two children. children replaced with left and right
adds sibling(v)

Question 3

what is depth and what is height

Answer 3

depth, number of ancestors excluding self

height, maximal depth

Question 4

what is a proper/full binary tree

Answer 4

either 0 or 2 children

Question 5

what is a complete tree

Answer 5

all levels full, except for last, where all nodes are as far left as possible

Question 6

what is a perfect tree

Answer 6

proper tree where all external nodes have equal depth

Question 7

what is an ordered tree

Answer 7

all elements left < right and stored element, and stored element < right

Question 8

what is a sparse tree

Answer 8

lots of empty elements

Question 9

how would a binary tree be represented using vector (array) represenation

Answer 9

A[0] = root
parent = A[(k-1)/2]
left child = A[2k+1]
right child = A[2k+2]

Question 10

how would a binary tree be represented in a linked structure

Answer 10

each node has: value, left pointer, right pointer

Question 11

what is a traversal

Answer 11

systematic way of visiting each node

Question 12

describe pre-order traversal

Answer 12

node then children

Question 13

describe post-order traversal

Answer 13

children then node

Question 14

describe in-order traversal

Answer 14

left then node then right

Question 15

describe depth first search

Answer 15

search children before sibling

Question 16

describe breadth first search

Answer 16

search cell nodes at same level before incrementing level

Question 17

what is a binary search tree

Answer 17

ordered binary tree

Question 18

describe balance

Answer 18

achieved y rotations

assures us about height

Question 19

describe when a single left rotation (LL) is performed and how

Answer 19

A becomes unbalanced when a node is inserted in the right subtree of A’s right subtree (B). We perform the left rotation by making A the left-subtree of B. A takes ownership of B’s left child as its right child
B takes ownership of A as its left child

Question 20

describe when a single right rotation (RR) is performed and how

Answer 20

the unbalanced node is inserted in the left subtree of C’s left subtree (B).

B becomes the new root.
C takes ownership of b’s right child, as its left child.
B takes ownership of C, as it’s right child

Question 21

describe a double left rotation

Answer 21

otherwise known as: left right

perform a right rotation on the right subtree
then left rotation on the root

Question 22

describe a double right rotation

Answer 22

otherwise known as: right left

performed when attempting to balance a tree which has a left subtree, that is right heavy

left rotation on leftsubtree.
then a single right rotation

Question 23

describe the height balance property

Answer 23

for every node, the heights of children may differ by at most 1