Prodtyping

The process on turning ideas into reality

December 31st 2018

Tree Data Structures

A data structure can be defined as a specialized format for accessing, organizing, and modifying data. There are lots of different data structures but the ones most commonly encountered in programming can be broken down into two camps.

Linear: a data structure where the elements form a sequence

  • Array
  • Stacks
  • Queues
  • Linked Lists
  • Hash Tables

Non-Linear: data structures which are stored in a hierarchical relationship.

  • Trees
  • Graphs

We're going to look more specifically at trees. What are some real-life examples of trees?

File systems

(This is of the Linux File System Structure)

Document Object Model (DOM)

Morse Code 

We can use trees for:

  • Manipulating hierarchical data
  • Manipulating sorted lists
  • Making information easier to search for (tree transversal)
  • Routing algorithms
  • And so much more! 

Terminology

  • Root is the first node of a tree
  • Edge is the link between two nodes
  • Parent is a node that has an edge to a child
  • Child is a node which has a parent
  • Leaf is a node which does not have a child
  • Height is the length of the longest path to a leaf
  • Depth is the length of the path to its root
  • Subtree are descendants of a node
  • Transversing is passing through nodes in a specific order
  • Levels are generations of a node
  • Keys are the value of a node based on a search operation

Other things about trees: 

  • A tree is set up hierarchically with data being arranged from more general to specific. 
  • Trees are made up of nodes which contain data or value and are connected by edges. 
  • Nodes can have child nodes but if they do not have any children they are called a leaf.
  •  Each leaf node will be unique.
  • Children nodes are independent of one another. 
  • The first node of the tree is the root. 
  • If the root is connected to another node then the root is also called a parent node and the connection is a child node. 
  • There can be multiple parent nodes on a tree but only one root.  If a tree has n-nodes then it will always have (n-1) edges.

Binary Trees

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Binary trees can be very useful for searching when they are balanced. Any node in the data structure can be reached by starting at the root node and repeatedly following references to either the left or right child. In a binary tree, a degree of every node is at most two. Depending on how nodes are arranged in a binary tree, it can be full, complete and perfect:

  • Full binary tree: each node has exactly 0 or 2 children (but never 1)and all leaf nodes are on the same level.
  • Complete binary tree: when all levels except the last one are full with nodes.
  • Perfect binary tree: when all the levels (including the last one) are full of nodes.

Binary Search Tree

Binary Search Trees or BST for short are a particular application of binary trees. BST has at most two nodes (like all binary trees). However, the values are in such a way that the left children value must be less than the parent and the right children is must be higher.

Transversal

Traversal describes the process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. There are different ways of traversing a Binary Tree depending on the order that the nodes are visited: in-order, pre-order and post-order.

  • In-Order Traversal: visit nodes on this order: left, parent, right.
  • Post-Order Traversal: visit nodes on this order: left, right, parent.
  • Pre-Order Traversal and DFS (Depth First Search): visit nodes on this order: parent, left, right

Conclusion

There are lots of different basic data structures that can be used in programming. Some data structures are linear and are useful for accessing data in a sequential manner. Linear structures have the drawback of taking a lot of time to search through for a data set. A tree is a data structure where a node has zero or more children. Trees with 2 children or less are called binary trees. If a binary tree is sorted where the left value is less than the parent and the right child is higher then it is considered a binary search tree. There is also a variety of ways to transverse a binary tree depending on the order in which nodes are visited.