What is a tree?

Tree is one form of a non-linear data structure that describes a hierarchical relationship (one to many) among the elements.

Picture by Paddy3118 - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=83223854

Tree can be defined as a collection of nodes with a specific element called Root and a reference to another node that is called Child. One node from a tree along with the nodes underneath it form a subtree. A subtree of a tree is caleld a tree.

C++ STL does not have implementations for Binary Search Tree

Terminology

Source: https://adrianmejia.com/images/tree-parts.jpg

• Root - First and top node on a tree.
• Edge - Reference that connects two node together.
• Child - Extension (node from underneath) from a node
• Parent - Node that is above another node. Every node has a parent excluding the root node.
• Siblings - set of two nodes or more with the same parent.
• Leaf - node that does not have a child.
• Internal node - all nodes that are not a leaf and root.

Binary Tree

Binary Tree is a tree in which each node has at most two child (left child and right child).

Source: https://media.geeksforgeeks.org/wp-content/uploads/binary_tree-1.png

To Binary Search Tree >