One Pager Cheat Sheet

• A binary tree is a recursive structure composed of one Node with a key value and up to two child Nodes that can be traversed with a root pointer.
• A BST is a special type of binary tree where the key values are placed according to a defined rule; nodes in the left subtree have keys less than the parent, and keys in the right subtree have keys greater than the parent.
• Every node in a binary search tree at most has two children and duplicates can be added, but must be placed in the same subtree.
• A balanced BST is a Binary Search Tree in which the left and right subtrees differ in height by no more than 1.
• A binary tree can be rebalanced to become a balanced BST, thereby ensuring that all subtrees of a given node will differ in height by no more than one (1).
• Create a balanced BST tree from a sorted array based on the in-order traversal of the unbalanced tree for efficient balancing.
• We are creating an array from BST in-order traversal using a vector and also recursively creating a balanced BST using build method with the middle array element being the root node.
• We are building a balanced binary tree from arrays of different lengths to view the pseudo code in action.
• We can start balancing our BST by coding the build function, with 0 and n-1 as its starting and ending parameters, respectively.
• Before trying out the code, it is best to conduct a dry run to get an idea of the time and memory complexities (which are O(N)) of the inorder traversal algorithm.
• It is possible to convert an array into a balanced Binary Search Tree (BST) using inorder traversal to divide the array and create a root node and subtrees that differ in height by one.
• It is not possible to convert a BST to a balanced BST without using recursion, as there is no algorithm known to have a better time complexity than O(n log n).