types of traversals in a binary tree

There are three types of traversals in binary tree: pre-order, in-order and post-order

Lets take an example of BST

            20
    15              25
12      18      22      28

pre-order: visit each node before its children

public void preorder(BinaryNode root) {
  if(root !=  null) {
    System.out.println(root.element);
    preorder(root.left);
    preorder(root.right);
  }
}

Output: 20, 15, 12, 18, 25, 22, 28

in-order (applied only for binary trees): visit left sub-tree, node and then right sub-tree

public void inorder(BinaryNode root) {
  if(root !=  null) {
    inorder(root.left);
    System.out.println(root.element);
    inorder(root.right);
 }
} 

Output: 12, 15, 18, 20, 22, 25, 28
Note: If we notice the above elements they are all sorted which means the inorder traversal of any BST gives us the sorted elements.

post-order: visit each node after its children (left and right sub trees)

public void postorder(BinaryNode root) {
  if(root !=  null) {
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.element);
 }
} 

Output: 12, 18, 15, 22, 28, 25, 20
 

What is BIG(O) NOTATION

BIG O Notation is used to represent complexity of an algorithm in worst case scenario.

Complexity in computer programming can be defined in terms of time and space. Space complexity tells us how much space is going to be taken for a particular algorithm. Time complexity tells us number of iterations (indirectly time) that are required for the completion of an algorithm.

O(1) means It takes constant space/time irrespective of the size of the data structure

O(n) means the space/time complexity is proportional to the length of the data structure

When to use ArrayList and LinkedList in java

These two data structures(DS) operate exactly opposite in terms of read and write operations.

ArrayList: this is build from a basic array

read operation complexity: O(1)
This is always constant because we query for an element based on index and hence there is no search involved to reach to the required element.

write operation: O(n)
Any modifications will lead to the shift of elements in an array completely, it first creates new array with new size inserts elements prior to the position of element to be inserted, then inserts the current element and inserts remaining elements after it.
Ex: If we wanna add element at 1st position then we need to shift all elements 1 position to the right and then insert element at first position

Linked List: This is build from double linked list

read operation: O(n):
Since the traversal of this data structure is based on links we need to traverse from starting position till the point we encounter the element that we are searching for, since in BIG-O notation time complexity is worst case scenario, if the element we are looking for is at last position then read operation complexity will be proportional to the length of the DS, hence O(n)

write operation: O(1):
Just by changing the links we would be able to insert the element at any position at any place in the DS which consumes same time

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey