Binary Trees and Binary Search Trees

Question 1

how many children can a node have?

Answer 1

two children(left and right)

Question 2

what is a node with no children called?

Answer 2

leaf node

Question 3

a strict binary tree is what…

Answer 3

one that can have either 2 or 0 children

Question 4

what makes a complete binary tree?

Answer 4

a tree where all levels are filled except possible the last and all nodes are as left as possible

Question 5

what is the maximum number of nodes for every level i?

Answer 5

i = 2^i

Question 6

what is the max # of nodes in a binary tree with height h

Answer 6

2^(h+1) -1

Question 7

what is the perfect height of a binary tree given nodes?

Answer 7

h = log base 2 (n+1) -1

Question 8

when do you have a balanced binary tree?

Answer 8

when the difference between the heights of the left and right subtrees for every node is not more than k(mostly 1)

Question 9

what is the height of a binary tree?

Answer 9

the # of edges in longest path from root to a leaf

Question 10

what is the height of an empty tree?

Answer 10

-1

Question 11

what is the height of a tree with 1 node?

Answer 11

0

Question 12

what is a binary search tree?

Answer 12

a binary tree in which for each node, the value of all the nodes in the left subtree is lesser or equal to and the value of all the nodes in the right subtree is greater.

Question 13

how do you create the node class for a BST?

Answer 13

protected static class Node {
public E data; // The information stored in this node.
public Node left; //Reference to the left child
public Node right; //Reference to the right child.

public Node(E data) {
            this.data = data;
            left = null;
            right = null;
        }

Question 14

how do you initiate the root node of BT?

Answer 14

protected Node root;

Question 15

how do you set the root node of a class to be null?

Answer 15

public BinaryTree(){ //BinaryTree is the name of the class
root=null;
}

Question 16

how do you set the root node of to equal this node?

Answer 16

public BinaryTree(Node root){
this.root=root;
}

Question 17

how do you set the root node of a BT to have data in it?

Answer 17

public BinaryTree(E data, BinaryTree leftTree, BinaryTree rightTree){
root = new Node<> data;
if(leftTree.root != null){
root.left=leftTree.root;
} else{
root.left=null;
}
if(rightTree!=null){
root.right=rightTree.root;
} else{
rightTree=null;
}
}

Question 18

how do you return the left subtree of a given tree?

Answer 18

public BinaryTree getLeftSubTree(){
if(root != null && root.left!=null){
return new BinaryTree(root.left);
}
else{
return null;
}
}

Question 19

how do you return the right subtree of a given Binary Tree?

Answer 19

public BinaryTree getRightSubTree(){
if(root != null && root.left !=null){
return new BinaryTree(root.right);
}
else{
return null;
}
}

Question 20

how do you return the data stored in the root node?

Answer 20

public E getData(){
if(root!=null){
return root.data;
}
else{
return null;
}
}

Question 21

how do you find out if a subtree is a leaf node(has no children)?

Answer 21

public boolean isLeaf(){
return if(root!=null && (root.right==null && root.left=null); // will return true if the node is a leaf node,, false otherwise

Question 22

what is preorder traversal?

Answer 22

pre order traversal is iterating through a node by going through its root, then its subtrees recursively

Question 23

How do you perform a recursive pre-order traversal on a binary tree?

Answer 23

public void preOrderTraverse(){
preOrder(root);
}

public void preOrder(Node node){
if(node==null){
return;
}
else{
System.out.println(node.data + " ");
preOrder(node.left);
preorder(node.right);
}
}

Question 24

what is post order traversal?

Answer 24

processing through all the subtrees, then processing through the root node

Question 25

how do you perform a post-order traversal?

Answer 25

public void postOrderTraverse(){ postOrder(root); } ``` public void postOrder(Node node){ if(root==null){ return; } else{ postOrder(node.left); postOrder(node.right); System.out.Println(" " + node.data(; } } ```

Question 26

what is in order traversal?

Answer 26

processes all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree.

Question 27

how do you perform an in order traversal?

Answer 27

public void inOrderTraverse(){ inOrder(root); } ``` public void inOrder(Node node){ if(node==null){ return; } else{ inOrder(node.left); System.out.println(" " + node.data); inOrder(node.right); ```

Question 28

how do you find the height of a BT?

Answer 28

``` public int treeHeight(){ return height(root); } ``` ``` private int height(Node node){ if(node==null){ return 0; } else{ return (1+max(height(node.left), height(node.right)); } } ```

Question 29

how do you count nodes in a binary tree?

Answer 29

``` public int nodeCount(){ return nodeCount(root); } ``` ``` private int nodeCount(Node node){ if(node==null){ return 0; } else{ return (1+nodeCount(node.left) + nodeCount(node.right)); } } ```

Question 30

how do you insert a node into a binary tree?

Answer 30

``` public void insertNode(E item){ Node node = new Node(item); Node parent=null, current; int randNum=0; Random rand = new Random(); if(root=null){ root=null; } else{ current=root; while(current!=null){ parent=current; randNum=rand.nextInt(2); //generates a random number between 0 or 1 if (randNum==0){ current=current.left; } else{ current = current.right; } //to link a new node as a leaf node if(randNum==0){ parent=parent.left; } else{ parent=parent.right; } } ```