Trees – Simple Operations and Traversal.

Trees

This article is a simple summary of most frequently performed operations over tree data structure. As an enterprise Java developer I don’t usually deal with traverse or other calculations with trees, There are already well designed and tested libraries to do the job. However, interviewers usually like to ask these questions and give you task or two – to be done on paper- that involves these operations.

For basic definitions of trees check my previous article. 

 

Trees Nodes
Tree Nodes

 

This factory creates the simple tree in the picture: 

Find the high of tree.

Pre-order tree traversal

Traversing a tree means visiting its node, to find if some value exists in that tree.

Pre-order traversing means do something with the current node (visit the node),display the value of it for example , traverse the left sub-tree then the right sub-tree recursively.

Algorithm: 

  • Display the data part of the root (or current node).
  • Traverse the left subtree by recursively calling the pre-order function.
  • Traverse the right subtree by recursively calling the pre-order function.

Post-order

The root node is visited last. First left subtree is traversed, then right subtree and finally root.

Algorithm: 

  • Traverse the left subtree by recursively calling the post-order function.
  • Traverse the right subtree by recursively calling the post-order function.
  • Display the data part of the root (or current node).

Outcome: 7 > 0 > 5 > 8 > 7 > 1 > 3 > 5 >

In-order

Algorithm:

  • Traverse the left subtree by recursively calling the in-order function.
  • Display the data part of the root (or current node).
  • Traverse the right subtree by recursively calling the in-order function. 

Outcome: 8 > 7 > 5 > 0 > 7 > 5 > 3 > 1 >

Graph Algorithms – Definitions.

Grapths Algorithms

This post represents a brief introduction to graph algorithms. When study I usually use to use paper and write a summary for what I read to better understand, analyze, and memorize what I am studying. 

Instead of using paper, this time, I decided to use my nice little blog as someone else can benefit from it. Reference of the definitions and books are provided at the end of this post. 

My mind, on the other hand, better works by visualizing things so I’ve done my best to draw pictures of the definitions mentioned in this post. 

1- Graph: graph G = (V, E) consists of a set of vertices, V, and a set of edges, E.

  •  Each edge is a pair (v, w), where v, w ∈ V. Edges are sometimes referred to as arcs.

Graph

  • There are two type of graphs, directed and undirected

directed graph

  •  Directed graphs are called digraphs. 
  • Vertex w is adjacent to v if and only if (v, w) ∈ E. In other words if the w and v are connected with only one edge. The edge E is consisted of w and v.

adjacent

  • In an undirected graph E is represented either by (v,w) or (w,v), the direction is both ways, it is undirected right ? 

different edge

  • In a directed graph (v,w) is a different edge than (w,v).
  • An edge can have a weight or sometimes called cost. In a geographical  map this can represent the distance between two points, for example. 

fifth -Weight

2- Path: A path in a graph is a sequence of vertices w 1 , w 2 , w 3 , . . . , w N such that (w i , w i+1 ) ∈ E for 1 ≤ i < N. 

  • The length of such a path is the number of edges on the path, which is equal to N − 1 
  • There is always a path from every vertex to itself and its length is 0, this is intuitive.
  • loop, this represents an edge (v, v) i.e a path from a vertex to itself.  

Path

  • A simple path is a path such that all vertices are distinct, except that the first and last could be the same. (wiki definition: a simple path is a path in a graph which does not have repeating vertices)   

simple path

3- Cycle: A cycle in a directed graph is a path of length at least 1 such that w 1 = w N ; this cycle is simple if the path is simple. In other, more intuitive words a cycle is a path that ends at the same vertex that it started from. 

a cycle

  • The is no cycles in an undirected graph, why is that? well because very edge is considered as a a cycle as it has both way from v -> w and from w->v. 

No cycles in directed graphs

  • A directed graph is acyclic if it has no cycles 

acyclic if it has no cycles

  • A directed acyclic graph is sometimes referred to by its abbreviation, DAG 

4- Some more points :  

  • An undirected graph is connected if there is a path from every vertex to every other vertex. 
  • A directed graph which is connected (there is a path from every vertex to every other vertex) is called strongly connected.
  • If a directed graph is not strongly connected (there is NO a path from every vertex to every other vertex), but the underlying graph the one without direction to the arcs or in other words the same graph after removing directions of edges is connected, then the graph is said to be weakly connected. In other words, a directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. 
  • A complete graph is a graph in which there is an edge between every pair of vertices 

5- References: 

Trees – definitions with pictures

This article depicts fundamental definitions of trees. It is an introduction to a series of articles dedicated to trees and their definitions in a simple and understood approach. Some people, like me, understand better with picture, they tend to draw a lot when explaining to others or themselves. Also, they tend to do a lot of hand motions when explaining something. The following summarized definitions are fundamental to understand trees.  

A Tree is a collection of nodes

 

Tree
Tree

One is called root, and zero or more nonempty children.

 

 

Each child or group of children can be considered a tree or a sub-tree of the main tree, thus each child of the main tree can be seen as a root.

   

A link between a root and its child is called edge If a tree has N nodes then it has N-1 edges, the red numbers on the images show edges nodes :

edge
Tree Edges

Leaves: nodes with no children

.  

Siblings: Nodes with the same root.  

siblings
Siblings

A path from node n 1 to n k is defined as a sequence of nodes n 1 , n 2 , . . . , n k such that n (i) is the parent of n (i+1) for 1 ≤ i < k The length of this path is the number of edges on the path, namely k − 1  

path
Length of a path

The depth of n i is the length of the unique path from the root to n i . Thus, the root is at depth 0

depth
Depth

 The height of n i is the length of the longest path from n i to a leaf. The height of a tree is equal to the height of the root.  

height
Height

If there is a path from n 1 to n 2 , then n 1 is an ancestor of n 2 and n 2 is a descendant of n 1 . If n 1 = n 2 , then n 1 is a proper ancestor of n 2 and n 2 is a proper descendant of n 1 .