A binary tree is a data structure that allows two nodes to be linked together by a path from the root to the leftmost child, and from the leftmost child to the rightmost child. The path is called a path from the root to the leftmost child, and from the leftmost child to the rightmost child.
A binary tree is a recursive data structure, meaning that it can be defined in terms of itself. A binary tree is a tree in which each node has two children. The root node is the topmost node in the tree. The left child is a node that is connected to the root node by a path from the root node to the leftmost child. The right child is a node that is connected to the root node by a path from the root node to the rightmost child.
The children of a node are sometimes referred to as the left child and the right child, respectively. The terms parent and child are also used to describe the relationship between nodes in a binary tree. A node is the parent of another node if the first node is connected to the second node by a path from the root node to the first node. A node is the child of another node if the first node is connected to the second node by a path from the first node to the second node.
The height of a node is the length of the longest path from the root node to the node. The height of a tree is the height of the root node.
The depth of a node is the length of the shortest path from the root node to the node. The depth of a tree is the depth of the root node.
A binary tree is said to be full if every node has either two children or no children. A binary tree is said to be complete if every node has two children or no children and all of the leaves are at the same depth.
A binary tree is said to be balanced if the height of the left subtree and the height of the right subtree differ by at most 1.
Here is an example of a binary tree:
1
/ \
2 3
/ \
4 5
The root node is 1. The left child of 1 is 2. The right child of 1 is 3. The left child of 2 is 4. The right child of 2 is 5.
The depth of the root node is 0. The depth of the node 2 is 1. The depth of the node 3 is 1. The depth of the node 4 is 2. The depth of the node 5 is 2.
The height of the root node is 2. The height of the node 2 is 1. The height of the node 3 is 1. The height of the node 4 is 0. The height of the node 5 is 0.
The tree is full. The tree is complete. The tree is balanced.