Tree Flashcards
What is a tree?
- Use to represent data in a hierarchical Format
- Every node(ideally) has 2 component(data and reference)
- Binary Tree: A tree that has nodes with either 0,1 or 2 children nodes. Its a family of DS (red black, AVL, BST, Heap tree, huffman etc.)
Tree Terminology
- Root: node with no parent
- Edge: link from parent to child
- leaf: node with no children
- sibling: nodes with the same parent
- Ancestor: parent, grandparent, and so on of a node
- Depth of node: length of a path from the root node
- Height of node: length of a path from that node to the deepest node
- Depth of tree: same as the depth of root node
- Height of tree: same as the height of the root node
- Predecessor: Immediate previous node in order traversal of the Binary tree
- Successor: Immediate next node in an in-order traversal of the Binary tree
Why use a tree data structure?
Array perform poorly in space efficiency
LL perform poorly on an insert, delete, traverse, search
For better time complexity.
Binary tree is a pre-req for other types of trees like (red black, AVL, BST, Heap tree, huffman etc.)
used to solve problems like
huffman coding
heap(priority queue)
Expression parsing
types of Binary tree
- Strict Binary Tree: A tree where each node has 2 or none children
- Full Binary Tree: If all non-leaf node has 2 children and all leaf node are at the same level
- Complete Binary Tree: If all levels are completely filled except possibly the last level and last level keys areas left as possible
How can be tree represented in a data structure
- via LL (with each node having left and right pointer)
- via Array:
0th index always left blank
root node always in cell 1
left node: with formula cell[2x], where x is the parent nodes cell index
right node: with formula cell[2x + 1], where x is the parent nodes cell index
Binary tree common operations
- Creation of Tree
- Insertion of node
- Deletion of node
- Traversal of all nodes
- Search of a node
- Deletion of Tree
How to traverse a Binary tree
- Depth first (Uses stack)
- pre-order
- post-order
- in-order
- Breadth first (Uses Queue)
- level order
What is an algorithm for pre-order traversal
preorder(root) {
if (root === null) return "err";
else {
print root;
preorder(root.left);
preorder(root.right);
}
}
Time complexity: O(n)
Space complexity: O(n)
What is an algorithm for in-order traversal
inorder(root) {
if (root === null) return "err";
else {
inorder(root.left);
print root;
inorder(root.right);
}
}
Time complexity: O(n)
Space complexity: O(n)
What is an algorithm for post-order traversal
postorder(root) {
if (root === null) return "err";
else {
postorder(root.left);
postorder(root.right);
print root;
}
}
Time complexity: O(n)
Space complexity: O(n)
What is an algorithm for level-order traversal
levelorder(root) {
const queue = new Queue();
queue.enqueue(root);
while(!queue.isEmpty) {
queue.enqueue(root.left); // enqueue the left child
queue.enqueue(root.right); // enqueue the right child
console.log(queue.dequeue()) // dequeue and print
root = queue.topOfQueue; // set the root to the next element in the queue
}
}
Time complexity: O(n)
Space complexity: O(n)
Insertion operation algorithm
insertInBT(data) {
if (tree.isFull) return;
else {
//find the next empty spot in the array
tree.internalArray[topOfQueue] = data;
topOfQueue++;
}
}
Time complexity: O(1)
Space complexity: O(1)
Delete operation algorithm
- To delete the value from the tree, find the node that does not have any child node and replace the value with the node that needs to be deleted
function delete(root, value){
let desiredIndex, count = 0;
// look for index of current value
while(root) {
if (root === value) {
desiredIndex = count;
}
count++;
}
// if the value is found update the value of desiredIndex with topOfQueue value
// update topOfQueue to new index which one less than current.
if (desiredIndex > -1) {
tree.internalArray[desiredIndex] = tree.internalArray[topOfQueue];
topOfQueue--;
}
}
Time complexity: O(n)
Space complexity: O(1)
