Binary Trees Info

Question 1

What is a Generic method and what is it used for

Answer 1

a.) It is a method definiton having a special type parameter that may be used in place for types

Question 2

Define what a tree is?

Answer 2

A tree is a set of Nodes

Question 3

What is the distingushed Node in a tree if it is not empty

Answer 3

Root

Question 4

What is the External node called in a tree?

Answer 4

Leaf

Question 5

What is the internal node in a tree

Answer 5

A node with one or more children

Question 6

What is a path in a tree

Answer 6

A path from node Vi to node Vk is a sequence of nodes such that vi+1 for 1<=i<=k

Question 7

What is the length of a tree?

Answer 7

The length of the tree is the number of edges encountered so (k-1)

Question 8

What is the depth of a tree

Answer 8

The depth of any node is the length of the path from the root to the node

Question 9

What is an Ancestor and what is a descendant

Answer 9

If there is a path from V1 to V2 then V1 is ancestor of V2 and V2 is the descendant of V1

Question 10

What is the height of the tree

Answer 10

The height of the tree is the height of its root

Question 11

What does a tree node include

Answer 11

An element and nodes linked together

Question 12

What is the Special case of K-ary Trees

Answer 12

it is a tree whose nodes have at mose two children pointers – binary trees

Question 13

Define a Binary Tree

Answer 13

It is a rooted tree in which no node can have more than two children AND the children are distinguished as left and right

Question 14

What is a General Binary Tree

Answer 14

It is a tree where each node has a most two nodes

Question 15

What is a full binary Tree

Answer 15

A binary tree where every interior node has two children or is an external node

Question 16

What is a perfect Binary tree

Answer 16

A full binary tree that every external node is at the same level

Question 17

what is a complete binary tree

Answer 17

It is like the perfect binary tree, except the last level may not be full but is filled from left to right

Question 18

Define a Binary Search Tree

Answer 18

It is a binary tree in which at every node v the values stored in the left subtree is less than the values stored in the right subtree which is greater

Question 19

What function must a BST class implement

Answer 19

A compareTo because the elements in the BST nodes must be comparable . Therefore a comparable interface or class must be defined

Question 20

How do we find whether an element exist in a BST

Answer 20

a.) Traverse for only the match
b.) Otherwise not found so return null

Question 21

What is the Running time for BST

Answer 21

O(Log N)

Question 22

How do we Insert in a BST

Answer 22

Traverse down a tree until there is no subtree Then create a new node

Question 23

What is the three cases for Deleting a node in BST

Answer 23

a.) A node has no children
delete it do nothhing more
b.) A node has one child
skip the node so that the node points to the child
c. A node has two children
replace the nodes data with the smallest data in right subtree
recursively delete the node

Question 24

What functions does the Doubly linked List have

Answer 24

add, remove, isEmpty and etc

Question 25

Explain PreOrder Traversal in BST

Answer 25

If the previous node was a parent then the next node is the immediate left child

If we already visted the left child then the next node is the immediate right child

if the those children do not exist then we backtrack up the tree

Question 26

Explain the InOrder Traversal in BST

Answer 26

First we go as far left as possible from the root keep tracking the node we pass

At a leaf we process the node retun to its parent process it and then move to the right child

Question 27

Explain the postOrder traversal in BST

Answer 27

hFirst go far right as possible from the root until we reach a node with no left cild

If the node we stop at has a right child then we move to it the again descend to the left as far as possible and repeat

Question 28

What are some recursive functions to define for BST?

Answer 28

Is it a full binary tree
is it a perfect binary tree
height of a tree
Number of Interior
Number of exterior nodes

Question 29

What is the typical base case of BST

Answer 29

O(N)