Binary Tree Flashcards
Nodes
the elements themselves
Edges
Links between nodes
Parent vs Child
Parent is the top node, children are under it
Inner Node
Nodes that have both parent and child
Leaf node
node with no children
What do levels start at
root node is level 0
Rules of Binary Trees
Each node has at most 2 children
Balanced vs Not Balanced vs Perfect
Balanced - difference between the height of the left subtree and the right subtree is at most 1
Perfect - All parents have 2 children, all leaves are at the same level
Preorder, Inorder & Postorder Traversal
Preorder - root -> left subtree -> right subtree
Inorder - left subtree -> root -> right subtree
Postorder - left subtree -> right subtree -> root
Binary Search Tree
Every node has a key
All keys in the left subtree are less than the key
All keys in the right subtree are greater than the key
Complexity of Search for BST
Best Case: O(1) if it’s root
Worst Case: O(depth)
If its balanced - its O(log n), if its unbalanced its O(n)
How to insert a node in a BST
if current is None
current = create_node
elif key < current.key
current.left = recursive_call
elif key > current.key
current.right = recurisve_call
else: (meaning key == current.key)
raise Error (duplicate)
return current
Complexity of insert BST
Best case is O(1) - occurs when adding to left subtree and all elements are on right side or vice versa
Worst Case is O(Depth)*comp(< & >) - depends if its balanced or not
Deleting a node
- If it has no children - just remove the link
- If it has one child - then just update the corresponding side
- if it has two children - you need to find the nodes successor - i.e. the node with the next largest key - do this by moving one step to the right until u find a leaf - this can then substitute the deleted node
How to collect the leaves of the tree
If current is not None:
if current is a leaf: add to list
else: go left and go right recursive
