A tree is a non-linear data structure that is used to store hierarchal data, e.g. a family tree, a company employee structure. Similar to Linked Lists, a Tree is made up of nodes that store a value and pointers to other related nodes. Trees make it fast to retrieve and organize data on a computer.
Structure Of A Tree Data Structure
All Trees have a node at the top known as the root; all other nodes are descendants of the root node.
Some of the terms used to describe the relationship between nodes in a tree are:
Parent and Child
A parent node refers to the node that directly precedes another node. In the above image we can see that node  is a parent of nodes [5, 6, 7], which would also make nodes [5,6,7] children / child nodes of node . similarly, nodes [9, 10] are children of node  and node  is the parent of node .
Nodes that share a parent node are referred to as siblings. Note all nodes in a tree can only have 1 parent except the root node which has no parent. In the above image we can see that nodes [5, 6, 7] are siblings; so are nodes [9, 10].
A node with no child nodes is called a leaf node. Nodes [5, 6, 7, 8, 9, 10] are all leaf nodes.
Ancestor and Descendant
An ancestor of a node refers to nodes that share a direct reverse connection between a given node and the root node; you can think of them as grand parents. In the above image we can see that nodes [6, 2, 1] are ancestors of node , though node  is technically an ancestor of node  it is more clear to call it a parent node.
Descendants are the same principle, but backwards. Node  is a descendant of nodes [6, 2, 1]. As we mentioned before, all nodes are descendants of nodes  aka the root nodes.
Any node in a tree that has descendants can be considered a subtree. All subtrees are descendants of the root node e.g. node  and it's child nodes.
Height Of A Tree
The height of a tree refers to the number of nodes/edges between the root node and its last descendants or farthest leaf nodes. The height of the above tree is 3.
Depth Of A Node
The depth of a node refers to the number of nodes/edges between a given node and the root node. In the above image, the depth of node  is 2.
Types Of Tree Data Structure
There are a lot of tree type data structures, but we are just going to look at a few.
A general tree is a tree that has no restrictions on the number of child nodes a parent node can have, including the root node.
A binary tree is a tree whose nodes can have no more than 2 child nodes per parent node including the root node. The child nodes in a binary tree are called left and right child
Binary Search Tree (BST)
A BST is a tree whose nodes are sorted when created. The nodes are sorted based on whether they are greater than or less than their parent node. Nodes greater than their parent node are placed to the right, while nodes less than are placed to the left.
if you would like to know what other tree type data structures there are check out this article.
Uses/Application Of Tree Data Structures
Trees are used in computer file systems to keep track of folder structure.
BST are often used in search and sorting algorithms.
Domain name space (DNS) uses tree data structures to manage domain names.
Trees are used when rendering computer graphics.
Dictionary applications, autocomplete and spell check use trees.
Top comments (0)