A Gentle Introduction to Trees 🌳
July 14, 2018 ∙ 6 min 👓
Most of the time when people embark upon the journey of learning data structures, they get started with linear data structures like array, stack, linked list, queue etc. And if the journey “continues”, they acquaint themselves with nonlinear data structures like trees and graphs. Fortunately, I continued the journey and stumbled upon an infamous nonlinear data structure called Tree. In this series of post, we’ll take a closer look at trees and different types of trees like Binary Tree, Binary Search Tree.
Let’s first understand linear and nonlinear data structures before starting with trees.
Linear Data Structure:
“A data structure is a linear data structure if its data items(elements) form a sequence or a linear list”.
In plain English, linear data structures have a logical beginning and a logical end. Examples: array, stack, linked list, queue.
NonLinear Data Structure:
Unlike linear data structures, elements of a nonlinear data structure do not form a sequence because of that they can be traversed in any desired order or nonsequential order. Examples: Tree, Graph etc.
As a programmer, we often need to decide which data structure to use. Should we use a linked list ? or should we use a stack? Or Should we always use an array? Well, the choice of data structure depends upon the circumstances.
“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” ~ Linus Torvalds
One may take the following factors into considerations:
 What needs to be stored ?
 Memory usages or consumptions.
 Ease of implementation.
Let’s address the elephant in the room. Trees are basically nonlinear data structures which are mostly used to organize data in a hierarchical way. Let’s take some of the real life examples.
Here the Stark Family Tree from Game of Thrones.
By looking at this tree, we can easily define relationships between each character.
We can say that Rickard
and Unknown
(yet to be revealed) are grandparents of Arya
and her siblings i.e. Robb
, Sansa
, Bran
, Rickon
, and Eddard
& Catelyn
are their parents.
Also Arya
and Jon Snow
are cousin cause their parents are siblings. I hope Jon Snow
at least knows this 😄.
Here’s another example which shows tree of a directory on file system.
Tree Terminology:
Sample tree

j < root
/ \
f k
/ \ \ < edge
a h z < leaves

node
: A basic entity in tree which can containdata
orvalue
and references to othernodes
. We can say, a tree is collection of these nodes. In above sample treej
,f
,k
,a
,h
, andz
are nodes of the tree. 
root
: is the top most node of a tree.j
is the root node. 
children
:f
andk
are children ofj
. Similarlya
&h
are children off
whilez
is child ofk
. 
parent
:j
is parent off
andk
, and grandparent ofa
,h
andz
. 
sibling
: children which have same parent are called sibling.f
andk
are sibling.a
andh
are also siblings. Butz
is cousin ofa
andh
cause their parents are siblings. 
leaf
: A node with no child is calledleaf
node. Herea
,h
andz
are leaf node. 
edge
: Nodes are connected by edges. Sometimes edges are also referred aslinks
.
Tree Properties:
Sample tree

j < root  L0
/ \
f k  L1
/ \ \
a h z  L2

A tree with
n
nodes will have exaclyn1
edges or links (Tree with only root node has0
link/edge). In the sample tree, we have 6 nodes and 5 edges (6  1). 
The Depth of node
x
= length of the path from theroot
to nodex
. Length of a path is basically the number of edges in the path. So we can say that the depth of nodex
is the number of edges in the path from theroot
tox
. The depth of the root node is 0. In the sample tree, depth of nodesf
andk
is 1, and depth of nodesa
,h
andz
is 2. Nodes with the same depth have the same level the in tree. We can seef
andk
have the same depth and they are at the same level L1. 
The Height of node
x
= number of edges in the longest path fromx
to aleaf
node. The height of aleaf
node is 0 and the height of an empty tree is considered as 1. The height of a tree can be defined by the height ofroot
node.
Note: In some books, the depth of a node x
is referred to the number of nodes in the path from the root
to node x
. In that case, depth of the of the root
node will be 1. Similarly, the height of the node x
is also referred as the number of nodes in the longest path from node x
to leaf
node which means the height of leaf node will be 1 and height of empty tree will be 0 instead of 1. In this series of posts, we will consider this definition of height and depth. You can read detailed discussion on depth and height here.
Another notable property of trees which make them superpowerful is their recursive nature.
Yes, Trees are recursive in nature.
It means that a tree is composed of many small trees called subtree
. If we ignore root node then every node in a tree represents a subtree. This property of trees helps us to write recursive algorithms for many operations like search and traversal, which are extremely simple to grok and implement.
Applications:
Here are some common uses of trees taken from Wikipedia.
 Representing hierarchical data.
 Storing data in a way that makes it efficiently searchable .
 Representing sorted lists of data.
 As a workflow for compositing digital images for visual effects.
 Router algorithms.
Here’s a sample Tree class with a countLeaves method which counts the number of leaf nodes in a tree inspired by Raganwald post on stinking recursion.
class Tree {
constructor(...children) {
this.children = children;
}
countLeaves() {
if (!this.children.length) {
return 1;
}
return this.children.reduce((leaves, child) => {
return leaves + child.countLeaves();
}, 0);
}
}
const tree = new Tree(new Tree(new Tree()), new Tree());
console.log(tree.countLeaves()); // 2 leaves
Hi, I am Hitesh.