A3 Theory W10 Flashcards
What is a binary tree? Explain the concept of nodes; including parent and child nodes. Given a binary tree containing N nodes, what is the maximum height such a tree can have? Explain in detail the invariants of a binary search tree.
A binary tree is an acyclic, connected graph. The parent nodes in a BT have at most two child nodes, referred to as the left and right child node. Nodes contain data, pointer to the left child node and pointer to the right child node. A node can be a child node and parent node at the same time. A root node has no parent nodes and at most, two children nodes, a leaf node has no children nodes.
Maximum height of a binary tree containing N nodes is n-1. If a tree had 3 nodes, the maximum height of the tree would be 2.
Invariants of binary search tree:
- each parent node has at most two child nodes
- For each parent node, the left child node is equal or lesser than the parent node, the right child node is greater than or equal to the parent node.
How many children does a non-leaf node have in a binary tree? How many parents does a non-root node have in a binary tree? Explain what makes a tree balanced or unbalanced.
A non-leaf node has at most two child nodes. A non-root node always has one parent node.
A tree is balanced when the absolute difference of height and width of left and right subtrees at any node is less than 1.
A tree becomes unbalanced when it is greater than 1.
Explain briefly how in-order/pre-order/post-order traversal works in a binary tree. Use an example each to help explain.
In-order traversal is a tree traversal technique which follows Left-Root-Right traversal pattern.
Example:
1
23
45 67
For inorder traversal, the above tree will be traversed in the following way: 4,2,5,1,6,3,7.
Pre-order traversal is a tree traversal technique that follows Root-Left-Right traversal pattern.
Example:
1
23
45 67
For preorder traversal, the above tree will be traversed the following way: 1,2,4,5,3,6,7
Post-order traversal is a tree traversal technique that follows Left-Right-Root traversal pattern.
Example:
1
23
45 67
For postorder traversal, the above tree will be traversed the following way: 4,5,2,6,7,3,1
Describe the concept of Expression Tree? What are the properties of Expression Trees? Give in/post/pre order example.
An expression tree is a representation of expressions arranged in a tree like structure.
An expression trees properties are a binary tree where each inner node corresponds to an operator and each leaf node corresponds to the operand.
What is the worst-case complexity of the insertion, deletion, and lookup operations on a BST? Elaborate for each case.
Lookup operations:
Best-case: O(1)CompEq - where the element is at the root, CompEq is the complexity of comparison
Worst-case: O(Depth)CompEq - where depth is the tree depth, this is dependent on how balanced the tree is. An unbalanced tree can cause O(n)*CompEq complexity.
Insert:
Best-case: O(1)Comp< OR >, depending on whether the nodes are in the right or left subtree.
Worst-case: O(depth)(Comp<+Comp>) so a balanced tree would be: O(log n)(Comp<+Comp>)
Unbalanced tree would be: O(n)(Comp<+Comp>)
Deletion:
Describe the TreeSort sorting algorithm. Explain what operations of a BST are used by this algorithm? Provide and analyse the best-case and worst-case complexity of TreeSort. Is there a way to improve the worst-case?
Tree sort is a sorting algorithm based on a binary search tree data structure. I first creates the binary search tree from the input list or array and then performs an in-order traversal on the binary search tree to get the elements in order.
The insertion and search operations are used by this algorithm.
Best case is O(log n) for adding one element so O(n log n) for adding n elements.
Worst case is O(n2) where n is the number of nodes in the tree - this is when the tree is unbalanced, if the tree is balanced then same as best case.
