- Node: A fundamental part of a tree that holds a value and may have a reference to other nodes (child nodes).
- Root: The topmost node in a tree, from which all other nodes are descended. It’s the starting point when traversing the tree.
- Parent: A node that has child nodes connected to it.
- Child: Nodes directly connected to another node when moving away from the root.
- Leaf: A node that does not have any children.
- Subtree: A tree within a tree. It consists of a node in the original tree and all of its descendants.
- Depth: The length of the path from the root to a particular node.
- Height: The length of the longest path from a node to a leaf. Alternatively, the depth of the deepest node.
- Binary Tree: A tree data structure in which each node has at most two children, referred to as the left child and the right child.
- Binary Search Tree (BST): A type of binary tree in which the left child node contains a value less than its parent node, and the right child node contains a value greater than its parent node. This property makes searching efficient.
Now, let’s delve into Binary Tree Representation:
Binary Tree Representation:
Binary trees can be represented in various ways. One common way is using a linked structure, where each node has references to its left and right children.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Creating a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
In this representation:
- Each node contains a value.
- Nodes have references (pointers) to their left and right children.
- A node without a child has its left and right attributes set to
None
.
Binary trees can also be represented using arrays or lists, where each index corresponds to a node, and the relationship between parent and child nodes is determined by the index. This representation is known as an array representation or sequential representation of binary trees.
For example, in an array representation, for a node at index i:
- Its left child is at index 2*i + 1.
- Its right child is at index 2*i + 2.
This representation saves memory but may require additional logic to handle cases where the tree is not complete.