Data Structures — Binary Tree
⚠️ This article has moved to my website.
You can read the latest version here:
👉 https://henriquesd.com/articles/data-structures-binary-tree
Below is a short preview of the article.
A Binary Tree is a hierarchical data structure consisting of nodes, where each node can have up to two children, commonly known as the left child and the right child. In this article, I explore the fundamental concepts of a Binary Tree and demonstrate the main traversal strategies using code examples in .NET.
Binary Tree
These are some important terms related to a Binary Tree:
- Node: it represents a termination point in a tree.
- Root node: it is the top node of the Binary Tree.
- Branch: it refers to the connection or path between nodes within the tree structure, it represents the relationship between a parent node and its child node(s). It is also used the terms “root branch” for the topmost node of the tree, “left branch” for a branch that connects a parent node to its left child node, and “right branch” for a branch that connects the a parent node to its right child node.
- Parent node: it is a node (except the root) in a tree that has at least one node.
- Child node: it is a node that is connected to a node above it.
- Leaf node: it is a node that has no children, and is located at the bottom level of the tree.
- Internal node: it is a node that has at least one child.
- Depth: it is the number of edges on the longest path from the root node to that node.
- Height: it is the length of the longest path from the root node to a leaf node.
Node
In a binary tree, a node is a block that represents a single element of data within the tree. Each node contains two main components:
- Data: which can be of any type (i.e.: integer, a string, an object, etc).
- References to Children: each node in a binary tree can have at most two children: a left child and a right child. Nodes are connected to each other through these references, forming the hierarchical structure of the binary tree.
A Binary Tree has these three characteristics:
- Has exactly one root.
- Each node has at most two children.
- Has only one path (a connection) between the root and any node.
Binary Tree Example
Below you can see a graphical representation of a Binary Tree. This is an example of a binary tree, but the tree could be bigger or smaller:
- Node 1 is the root node.
- Node 1 contains 2 children: node 2 (left node) and node 5 (right node).
- Node 2 contains two children: node 3 (left node) and node 4 (right node).
- Node 5 contains only one child: node 6 (right node).
- Nodes 3, 4 and 6 are the leaf nodes.
TreeNode
This is a representation of a TreeNode class in C#:
👉 Continue reading the full article here: https://henriquesd.com/articles/data-structures-binary-tree
