Trees
- A tree is a node based data structure.
- Each node can have links to multiple other nodes
- Compare this to a singly linked list which can only link to the next node or a double linked list which can only link to the previous and next nodes.
- All the nodes in a tree must be connected
- There cannot be any cycles in a tree (i.e. two nodes cannot link to the same child node)
- A tree is balanced when the following 3 conditions are met:
- The left and right subtrees heights differ by at most 1
- The left subtree is balanced
- The right subtree is balanced
- A tree is perfectly balanced when the left and right subtrees of any node are the same height.
Example of a tree. This is NOT a binary tree as the 7 node has three child nodes. This is an imbalanced tree. Attribution: Paddy3118, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons
Example of a balanced binary tree. Attribution: User:Mikm, Public domain, via Wikimedia Commons
A binary tree is a tree where each node can have zero, one or two children.
Unbalanced and not sorted binary tree. Attribution: Radke7CB, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons
A binary search tree is a binary tree that has these properties:
- Each node can have at most one left and one right child
- The left descendants must only contain values that are less than the node
- The right descendants must only contain values that are greater than the node
- Each subtree must be a valid binary search tree.
- If the node to delete has no children, then just delete it
- If the node to delete has one child, delete the node, and put the child node where the deleted node was.
- If the node to delete has two children, then replace it with successor node. The successor node is the node with the least value of the child nodes that are greater than the deleted node.
- To find the successor node: visit the right child of the deleted node. Traverse down the left branch of all child nodes until a node does not have a left child. That node is the successor node.
- If the successor node has a right child, then after placing the successor node in its new spot, move the right child to the left side of the successor's former parent
- Example of finding the successor node:
- Suppose we want to delete 3 from the above diagram. We would delete the 3, then move to the right child, 6. We, then traverse down the left branches. In this case, there is only one, 4. Node 4, moves to where node 3 was.
Four ways to traverse a tree are:
- Preorder
- Inorder
- Postorder
- Level order
The first 3 traversals (preorder, inorder and postorder) use Depth First Search to traverse the tree. Where the node is processed in relation to traversing the children determines the type of traversal. Level order traversal uses Breadth First Search to traverse the tree.
The tree is traversed in the order: Node -> Left -> Right
8, 3, 1, 6, 4, 7, 10, 14, 13
Using preorder traversal means the root node will be processed first.
def preorder(tree: TreeNode):
if node is None:
return
print(node.value)
preorder(node.left)
preorder(node.right)
The tree is traversed in the order: Left -> Node -> Right
1, 3, 4, 6, 7, 8, 10, 13, 14
Using inorder traversal on a binary search tree will traverse the nodes in ascending order.
def inorder(tree: TreeNode):
if node is None:
return
inorder(node.left)
print(node.value)
inorder(node.right)
The tree is traversed in the order: Left -> Right -> Node
1, 4, 7, 6, 3, 13, 14, 10, 8
Using postorder traversal means the root node will be processed last.
def postorder(tree: TreeNode):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.value)
The tree is traversed level by level: Level 0 -> Level 1 -> Level 2 etc
8, 3, 10, 1, 6, 14, 4, 7, 13
def level_order(tree: TreeNode) -> List:
queue = deque()
result = []
queue.append(tree)
while queue:
node = queue.popleft()
if node:
result.append(node.value)
queue.append(node.left)
queue.append(node.right)
return result
- A kind of tree that is good for text-based features such as autocomplete
- It is NOT a binary tree. It can have multiple child nodes.
-
Last modified 1yr ago