Trees Flashcards
1
Q
What is a Binary Tree?
A
An ordered tree where left child is less than parent and parent is less than right child.
Parent nodes only have 2 or less children.
2
Q
How to add a Node recursively?
A
void add(int val)
{
this.root = addNode(val, this.root);
}
private Node addNode(int val, Node node){
if (node == null) {
node = new Node(val);
return node;
}
if (val < node.val) {
node.left = addNode(val, node.left);
}
else if (val > node.val) {
node.right =addNode(val, node.right);
}
return node;
}
3
Q
How to Lookup recursively?
A
boolean lookup (int val)
{
return lookupRecurse(root, val);
}
boolean lookupRecurse(Node root, int data)
{
boolean isThere = false;
if (root == null) return false;
if (data == root.val ) isThere = true;
if (data > root.val) isThere = lookupRecurse(root.right, data);
else if (data < root.val) isThere = lookupRecurse(root.left,data);
return isThere;
}
4
Q
How to iteratively LookupBFS?
A
boolean lookupBFS (int val)
{
Queue q = new LinkedList();
q.add(root);
while(!q.isEmpty())
{
Node tmp = q.remove();
if (tmp.val == val)
{
return true;
}
if (tmp.left != null)
q.add(tmp.left);
if (tmp.right != null)
q.add(tmp.right);
}
return false;
}
5
Q
How to iteratively LookUp DFS?
A
boolean lookupDFS(int val)
{
Stack s = new Stack();
s.push(root);
while(!s.isEmpty())
{
Node tmp = s.pop();
if (tmp.left != null) s.push(tmp.left);
if (tmp.right != null) s.push(tmp.right);
if (tmp.val == val) return true;
}
return false;
}
6
Q
What are the types of Ordering?
A
Preorder: M,L,R
Inorder: L,M,R
Postorder:L,R,M
7
Q
How to delete a node?
A
void delete(int val)
{
root = deleteRecursive(val, root);
}
private Node deleteRecursive(int val, Node root)
{
if (root == null ) return null;
System.out.println("Hunting: "+ val + " Found: " + root.val);
if (root.val == val)
{
System.out.println("Found");
if (root.left == null) System.out.println("No left");
if (root.right == null) System.out.println("No right");
if ((root.left == null) && (root.right == null))
{
// If there are no children we can delete the node
System.out.println("Deleted no children" );
return null;
}
if (root.left == null)
{
// if there is only the right node, set the right node as replacement of deleted
System.out.println("Deleted no left" );
return root.right;
}
if (root.right == null)
{
// if there is only left, set the left to replace the deleted
System.out.println("Deleted no right" );
return root.left;
}
else
{
// if there is two children, we return the smaller parent to the top.
System.out.println("We got em");
int smallestVal = findSmallestVal(root.right);
root.val = smallestVal;
root.right = deleteRecursive(smallestVal, root.right);
return root;
}
}
if (root.val > val)
{
root.left = deleteRecursive(val,root.left);
System.out.println("left");
return root;
}
else if (root.val < val) {
root.right = deleteRecursive(val, root.right);
System.out.println("right");
return root;
}
return root;
}
8
Q
How to count nodes?
A
int nodeCount()
{
int count = nodeCountRecursive(root);
return count;
}
private int nodeCountRecursive(Node root)
{
int count = 0;
if (root == null) return 0;
if (root != null) count = count+1;
if (root.left != null) count = count + nodeCountRecursive(root.left);
if (root.right != null) count = count + nodeCountRecursive(root.right);
return count;
}
9
Q
How to get height?
A
int getHeight()
{
return getHeightRecurse(root);
}
private int getHeightRecurse(Node root)
{
int leftHeight = 0;
int rightHeight =0;
if (root == null) return 0;
leftHeight = getHeightRecurse(root.left)+1;
rightHeight = getHeightRecurse(root.right)+1;
return Math.max(leftHeight, rightHeight);
}
10
Q
How to check if a tree is a binary tree?
A
boolean isBTree()
{
return isBTreeRec(root);
}
private boolean isBTreeRec(Node root)
{
boolean left = false, right = false;
if (root == null) return true;
if (root.left == null && root.right == null) return true;
if (root.left !=null)
{
System.out.println("Left: " + root.left.val + " Mid: " + root.val);
if (root.left.val > root.val)
{
return false;
}
}
if (root.right != null)
{
System.out.println("Left: " + root.left.val + " Mid: " + root.val);
if (root.right.val < root.val)
{
return false;
}
}
left = isBTreeRec(root.left);
right = isBTreeRec(root.right);
if (left && right) return true;
return false; }
11
Q
How to get a Succesor Node? (Node that is above the value)
A
int getSuccessor(int val)
{
return getSuccessorRec(val, root);
}
private int getSuccessorRec(int val, Node root)
{
if (root == null) return -1;
if (val > root.val)
{
return getSuccessorRec(val, root.right);
}
if (val <= root.val && root.left == null )
{
return root.val;
}
if (val <= root.val && root.left != null)
{
if (root.left.val > val)
{
return getSuccessorRec(val, root.left);
}
else
{
return root.val;
}
} return root.val; }
12
Q
What is the access, search, deletion, insertion time for a B-Tree?
A
O(logn)
Every level, it removes an of the nodes from the search.
Worst case is O(n) in case where the tree resembles an array.
13
Q
What is a Node?
A
class Node {
int val;
Node left;
Node right;
public Node(int val){
this.val = val;
this.left = null;
this.right = null;
}
}
14
Q
Invert a Btree
A
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
15
Q
BTree Level Order
A
List> levelOrder(TreeNode root) {
List> l = new LinkedList();
int count = 0;
return levelOrderRec(root, l, count);
}
List> levelOrderRec(TreeNode root, List> level, int count)
{
if (root == null) return new LinkedList();
if (level.size() == count) level.add(new LinkedList());
List tmp = level.get(count);
tmp.add(root.val);
levelOrderRec(root.left, level, count+1);
levelOrderRec(root.right,level, count+1);
return level;
}
