Binary Tree use case.
In computer science and programming, a a tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. And a tree whose elements have at most 2 children is called a binary tree. We typically name these 2 children the left and right child.
A Binary Tree node contains the following 3 items:
- Pointer to left child.
- Pointer to right child.
A full Binary tree is a type of binary tree in which every parent has either two or no children.
A perfect binary tree is a type of binary tree in which every internal node has exactly two children and all the leaf nodes are at the same level.
A complete binary tree is a binary tree in which every level (except possibly the last) is completely filled and all nodes in the last level are as far left as possible.
A degenerate or pathological tree is where each parent node has only one child node, which is similar to a linked list data structure.
A balanced binary tree is a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Binary Tree traversal Python code:
class Node: def __init__(self, key): self.left = None self.right = None self.val = key def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("In order Traversal: ") root.traverseInOrder() print("\nPre order Traversal: ") root.traversePreOrder() print("\nPost order Traversal: ") root.traversePostOrder()
In order Traversal:
4 2 5 1 3
Pre order Traversal:
1 2 4 5 3
Post order Traversal:
4 5 2 3 1