Hierarchical Data Structure: Binary Tree
A binary tree is a hierarchical data structure with several key components and properties
A binary tree is a hierarchical data structure with several key components and properties. Understanding these components is crucial for working effectively with binary trees. Here’s an overview of the primary components and their roles:
1. Node
Each node in a binary tree contains:
- Value/Data: The actual data or value stored in the node.
- Left Child: A reference (or pointer) to the left child node. In binary trees, the left child is a subtree that contains nodes with values less than the current node's value (in binary search trees).
- Right Child: A reference (or pointer) to the right child node. In binary trees, the right child is a subtree that contains nodes with values greater than the current node's value (in binary search trees).
Here's how a basic node might be defined in Python:
python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
```
2. Root
The root is the top node of the binary tree. It is the starting point for all operations and traversals. There is exactly one root in a binary tree.
3. Leaf Node
A leaf node (or terminal node) is a node that does not have any children. In other words, both the left and right child pointers of a leaf node are `None`.
4. Internal Node
An internal node is any node that is not a leaf. It has at least one child, either left, right, or both.
5. Subtree
A subtree is a portion of a binary tree that includes a node and all of its descendants. Each node in a binary tree can be considered the root of a subtree.
6. Depth
The depth of a node is the number of edges from the root node to that node. The depth of the root node is 0.
7. Height
The height of a node is the number of edges on the longest path from that node to a leaf. The height of the tree is the height of the root node.
8. Level
The level of a node is defined as the number of edges from the root to that node plus one. For example, the root node is at level 1, its children are at level 2, and so on.
9. Balanced Tree
A binary tree is balanced if, for every node in the tree, the difference in height between the left and right subtrees is no more than a certain value (often 1). Balanced trees help maintain efficient operations.
10. Binary Search Tree (BST)
A binary search tree is a type of binary tree with an additional property: for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.
Example of a Simple Binary Tree Structure in Python
Here’s an example that demonstrates a binary tree with nodes, root, leaf nodes, and internal nodes:
python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Create nodes
root = TreeNode(10)
node1 = TreeNode(5)
node2 = TreeNode(15)
node3 = TreeNode(3)
node4 = TreeNode(7)
node5 = TreeNode(12)
node6 = TreeNode(18)
Build the tree
root.left = node1
root.right = node2
node1.left = node3
node1.right = node4
node2.left = node5
node2.right = node6
Visual representation of the tree:
10
/ \
5 15
/ \ / \
3 7 12 18
Summary
- Node: Basic unit of a binary tree with value, left child, and right child.
- Root: The topmost node of the tree.
- Leaf Node: A node with no children.
- Internal Node: A node with at least one child.
- Subtree: A node and all its descendants.
- Depth: Distance from the root to the node.
- Height: The longest path from a node to a leaf.
- Level: Number of edges from the root plus one.
- Balanced Tree: A tree where the height difference between left and right subtrees is within a specified limit.
- Binary Search Tree (BST): A binary tree with the property that left children are less than the node, and right children are greater.
These components and properties form the foundation for various binary tree operations, such as insertion, deletion, and traversal.