What is a binary tree

A binary tree is a hierarchical data structure. A binary tree consists of nodes, each node has:

  • A left node
  • A right node
  • A data element, which could be of any type

Here's how a typical binary tree looks:

    public class Node
    {
        public int Value;
        public Node Left;
        public Node Right;

        public Node(int value)
        {
            Value = value;
        }
    }

A binary tree can be represented graphically

binary tree

Terminology used in trees:

  • Root: the node at the top of the binary tree
  • Child: a node below a given node
  • Parent: the converse definition of a child (the opposite of child)
  • Leaf: a node without child nodes
  • Edge: a connection between two nodes
  • Subtree: a tree representing the descendants of a node
  • Level: the level at which a node resides, its generation

 

binary tree

 

Another two definitions are:

  • Depth: the number of edges from the root to the node
  • Height: the number of edges from the node to the deepest leaf

 

binary tree

 

Video Lesson