Tree is the most widely used data structure for representing hierarchical data.

Tree Terminology

  • Root – The top node in a tree.
  • Child – A node directly connected to another node when moving away from the Root.
  • Parent – The converse notion of a child.
  • Siblings – Nodes with the same parent.
  • Descendant – A node reachable by repeated proceeding from parent to child.
  • Ancestor – A node reachable by repeated proceeding from child to parent.
  • Leaf – A node with no children.
  • Internal node – A node with at least one child
  • External node – A node with no children.
  • Degree – Number of sub trees of a node.
  • Edge – Connection between one node to another.
  • Path – A sequence of nodes and edges connecting a node with a descendant.
  • Level – The level of a node is defined by 1 + (the number of connections between the node and the root).
  • Height of node – The height of a node is the number of edges on the longest path between that node and a leaf.
  • Height of tree – The height of a tree is the height of its root node.
  • Depth – The depth of a node is the number of edges from the node to the tree’s root node.
  • Forest – A forest is a set of n ≥ 0 disjoint trees.

Applications

  • Represent Hierarchical data e.g File System, ancestory etc
  • Router algorithm
  • Easy Searching (Traversal)

Tree representation

1

//Have left and right node
//Have a value to store the value of the current node
class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val){
        this.val = val;
    }
}
public static void main(String args[]){
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
}

Tree Traversal

  • Level Order (Breadth first) (Visit each level at a time)
    • All the nodes of the current level will be visited first before going to the next level
    • In the above tree, the level order will display the node values in this order
      • 1234567

1

To find the levels we need to get the height of the tree

//if root is null then return 0
//find the left and right node height by recursing
//find the max of left and right node 
public static int height(TreeNode root){
        if(root == null)
            return 0;
        int lheight = height(root.left) + 1;
        int rheight = height(root.right) + 1;
        int height = Math.max(lheight,rheight);
        return height;
    }

//get the level order
//decrease the level and recurse, return if the level is 1    
public static void bfs(TreeNode root, int level){
        if(root == null)
            return;
        if(level == 1)
            System.out.println(root.val);
        else{    
                bfs(root.left,level-1);
                bfs(root.right,level-1);
            }
    }
  • InOrder Traversal (left-root-right)
    • left node will be visited first and then the root node and then the right node
      • the above tree will return 4251637

1

    //left root right
    //4251637
    public static void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
  • PreOrder Traversal (root-left-right)
    • root node will be visited first and then the left node and then the right node
      • the above tree will return 1245367

1

//root left right
    //1245367
    public static void preOrder(TreeNode root){
        if(root == null)
            return;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
  • PostOrder Traversal (left-right-root)
    • left node will be visited first and then the right node and then the root node
      • the above tree will return 4526731

1

//left right root
    //4526731
    public static void postOrder(TreeNode root){
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

 

Advertisements

Introduction

Stack is a very common data structures which will return in the element stored in a Last In First Out fashion.

Applications

  • Expression Evaluation
    • Post fix /In fix
  • Backtracking
    • Finding Paths
    • Game Playing
  • Exhaustive search
  • Memory Management
  • Depth First Search traversal

Here we will see how to implement a stack using Array and Linked List

Array Implementation

1

We can implement array with fixed capacity(bounded) or with dynamically allocating the memory for storing the elements(unbounded). If the size reaches the maximum element the size is doubled and the elements are copied to a new array

class ArrayStack{
    
    int size; // size of the array
    int[] array;
    int head; // head pointer
    int max; //max capacity
 
//initialize size, max and the internal array
  public ArrayStack(int max){
      this.array = new int[max];
      this.head = 0;
      this.size = 0;
      this.max = max;
  }
  
//return the current size
  public int getSize(){
      return size;
  }

//return true if the size == 0
  public boolean isEmpty(){
      return size == 0;
  }

//return the head of the stack
    public int peek(){
      return head;
  }  

//check for empty
//if not then update the head with the last array element that was inserted
//set the array element to 0 (reset)
//return the head
  public int pop(){
      if(!isEmpty()){
          head = array[--size];
          array[size] = 0;
          return head;
      }
          System.out.println("No Element");
          return -1;

  }

//set the array to the value inserted if the size is not equal to max
/set the head to last inserted element
//increment the size
  public void push(int val){
      if(size != max){
          array[size] = val;
          head = array[size];
          size++;
      }
      else
          System.out.println("Reached max element");
          //------------------Dynamic Allocation Code - START----------------
          //max = (max * 2) + 1; //simply doubling the size (dynamic allocation)
          //int[] tempArray = new int[max];
          //for(int i=0;i<size;i++){
          //  tempArray[i] = array[i];
          //}
          //array = tempArray;
          //array[size] = val;
          //head = array[size];
          //size++;
          //------------------Dynamic Allocation Code - END----------------
  }
}

public class ArrayStackLimitedImpl {
    public static void main(String[] args) {
       ArrayStack s = new ArrayStack(3);
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(4);
       s.push(4);
       s.push(4);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
    }
}

Linked List Implementation

1

class ListNode{
  ListNode next;
  int val;
  
  ListNode(int val){
    this.val = val;  
  }
  
}

class LinkedListStack{
    ListNode tail;
    int size;
   
//get the current size of the stack 
    public int getSize(){
      return size;
    }

//return true if size == 0
  public boolean isEmpty(){
    return size == 0;
  }

//return the top element  
  public int peek(){
    return tail.val;
  }

//pop the last inserted element if not empty
//store the top element by peek
//top will be pointing to the next element
//decrement the size
//return the top value  
  public int pop(){
    if(!isEmpty()){
      int val = peek();
      tail = tail.next;
      size--;
      return val;
    }
      System.out.println("No Element");
      return -1;

  }

//push the new element
//set the new node's next element as the previous top element
//set current top element as the new node
//increment the size
  public void push(int val){
    ListNode newNode = new  ListNode(val);
    newNode.next = tail;
    tail = newNode;
    size++;
  }
}

public class YourClassNameHere {
    public static void main(String[] args) {
       LinkedListStack s = new LinkedListStack();
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(7);
       s.push(8);
       s.push(9);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
      
    }
}

Test cases

  • Cannot pop if the stack is empty
  • In bounded stack if the size of the stack reaches max then it will not allow pushing further elements to the stack
  • peek should not pop the element

 

1Bitwise Operation

You have to be comfortable with Bitwise operations (<<, >>, &, | , ~, ^). Please have a look at the basics here.

These are the operations to summarize

& - bitwise and
| - bitwise or
~ - bitwise nor
^ - bitwise xor
<< - bitwise left shift
>> - bitwise right shift

In this section I will get to more detailed explanation of the operations that we have seen in the previous post and also techniques for some new operations.

Masking

Masking is very basic in bit manipulation and make sure you get that right before starting any bit level operations.

  • use left shift (<<) to increase the shift from LSB to MSB
  • use right shift (>>) to increase the shift from LSB to MSB

How to mask?

  • Take a number lets say x = 8; The binary representation for this for 8 bit register will be 0000 1000
  • Lets consider that we are masking this number with a mask which is at the 0th position, that will be 0000 0001 = 1
x(8)       0000 1000
mask(1)    0000 0001
------------------------------------
x & mask will give us 0000 0000 - 0
x | mask will give us 000 1001 - 9
x ^ mask will give us 000 1001 - 9

What if we want to mask the bit at the position 4

  • Left shift the mask 1 with 4. this will move the bit to the 4th position. from
  • mask = 1 << 4 = (0000 0001   <<  4)=  0000 1000

Now

x(8)            0000 1000
mask(1 << 4)    0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 000 1000 - 8
x ^ mask will give us 000 0000 - 0

This is enough to start with our first bit trick.

#1 . How to check if the Integer is even or odd

We know that

  • for even number we will have LSB set to 0 always
  • for odd number we will have LSB set to 1 always
x(3)    0000 0011
1       0000 0001
------------------------------------
x & 1 will give us 0000 0011 - 3

So with this trick we can come up with the code like

if((x & 1) == 0)
   //even
else
   //odd

#2 . Check if the n’th bit is set or not

  • we take the number, lets say x = 8   =>  0000 1000
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x & mask)
  • bit wise & will be 1 if both the bits are set to 1. If the output is 1 for that bit then the bit is set

case 1 – position  – 4

x(8)          0000 1000
mask(1 << 4)  0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 0000 1000 - 8

case 2 – position  – 3

x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x & mask will give us 0000 1000 - 0
x | mask will give us 0000 1100 - 12 (we cannot use |)

We can write code for this like

if(x & (1 << position))
   // bit is set
else
  // bit is not set

#3 . Set the n’th bit

  • we take the number, lets say x = 8   =>  0000 1000
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x | mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1
x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x | mask will give us 0000 1100 - 12
y = x | (1 << position)

#4 . Unset the n’th bit

  • we take the number, lets say x = 12   =>  0000 1100
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x & ~mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1.
x(12)                     0000 1100
mask(1 << 3)   0000 0100 
~mask(1 << 3)             1111 1011
---------------------------------------------------
x & ~mask will give us 0000 1000 - 8
y = x & ~(1 << position)

#5 . Toggle the n’th bit

  • we take the number, lets say x = 12   =>  0000 1100
  • prepare a mask for the nth position at which you want to check the bit
  • do the bit wise (x ^ mask)
  • for the position where the bit is 0 doing a bit wise | will set the bit to 1.
x(8)           0000 1000
mask(1 << 3)   0000 0100 
---------------------------------------------------
x ^ mask will give us 0000 1100 - 12
y = x  ^ (1 << position)

#6 Turn off the right most 1 bit

  • we take the number, lets say x =8   =>  0000 1000
  • subtract 1 from x (x – 1)
  • Bitwise & x and (x – 1)
x(8)         0000 1000 
x-1 (7)      0000 0111 
---------------------------------------------------
x & (x- 1) will give us 0000 0000 - 0 (4th position 1 is changed)
x(7)         0000 0111 
x-1 (6)      0000 0110
---------------------------------------------------
x & (x- 1) will give us 0000 0110 - 6 (0th position 1 is changed)
y = x & (x - 1)

#7 Turn on the rightmost 0 bit

  • we take the number, lets say x =8   =>  0000 1000
  • Add 1  to x (x + 1)
  • Bitwise | x and (x – 1)
x(8)         0000 1000 
x+1 (9)      0000 1001 
---------------------------------------------------
x | (x + 1) will give us 0000 1001 - 9
x(7)         0000 0111 
x+1 (8)      0000 1000
---------------------------------------------------
x | (x- 1) will give us 0000 1000
y = x | (x + 1)

#8 Isolate the rightmost 1 bit

  • we take the number, lets say x =8   =>  0000 1000
  • take -x (-x)
  • Bitwise & x and (-x)
x(11)         0000 1011 
-x (-11)      1111 0101         (~x + 1)
---------------------------------------------------
x & (-x) will give us 0000 0001 - 1
y = x & (-x)

#9 Isolate the rightmost 0 bit

  • we take the number, lets say x =8   =>  0000 1000
  • do the ~ of x
  • Bitwise & ~x and (x + 1)
~x(11)         1111 0101 
(x + 1)        0000 0110
---------------------------------------------------
~x & (x + 1) will give us 0000 0100
y = ~x & (x + 1)

Reference:
https://graphics.stanford.edu/~seander/bithacks.html
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

Bits are basically represented in either 1 or 0 so the each bit contains either of the 2 values

1

For integer which can hold 32 bits = 4 bytes

Integer max value
Decimal:  2147483648 – (2 power 31)
Binary: 10000000     00000000     00000000     00000000
Integer min value
Decimal: 2147483647 – (2 power 31) – 1
Binary: 11111111     11111111     11111111     11111111
Following table will help to visualize bits in detail
1
This code will give compile error
byte ch = 129; // byte will hold upto 127
No need to cast explicitly to change byte to int
int x = ch;
x = 2000; // now x can hold upto 2147483648
 you need explicit casting to change integer to byte and you will loose data
int x = 2000;
byte ch = (byte) x; // will reduce the value 2000 to 127;
Left Shift (<<)
  •  It is a bit wise operation which will let you shift the bit position.
  • We use this << operator for moving the bit to the position.
  • Left shift is equivalent to the number multiplied by 2
In the below table we move the ‘1’ from the least significant bit(LSB) to the position specified
 1
Right Shift (>>)
  • This is opposite the left shift where we move the bit to right
  • It is equivalent to dividing the number by 2

1.png

Bitwise AND (&)
This will do the AND operation at the bit level. The following code will check number of bits set for the given number
    int x = 65;
    int count= 0;
    while(x>0){
         x = x & (x - 1);
         count ++;
    }
Bitwise OR (|)
This will do the OR operation at the bit level. The following code will check if a bit is set at the given position
    int x = 8;
    int position = 3;
    int mask = 1 << position;
    System.out.println(x | mask);
Bitwise NOT (~)
This operator will help to clear a bit.
    int x = 8;
    int position = 3;
    int mask = 1 << position;
    System.out.println(x & ~mask);
Bitwise XOR (^)
We can use the XOR operator to toggle a bit.
   int x = 8;
   int position = 3;
   int mask = 1 << position;
   System.out.println(x ^ mask);

Memory Representation

Representation of boolean, char, Integer in memory

1.png

1

Boolean

  • (1/0) or (true/false) or (+/-) or (Yes/No)
  • used for checking if the given condition passes
  • used in logic checking (AND OR NOT)
  • represented as a binary digit or 1 bit (Java and size not precisely defined)

1

Array: boolean array – boolean[]

1

Byte

  • 8 bit signed two’s complement integer
  • -128 to 127
  • used to save memory for arrays
  • and in some time use in place of int also
  • Array: byte array – byte[]

Character

  • characters are letters, digits, special characters, control characters
  • in java these are 16 bits Unicode characters from ‘\u0000’ to ‘\uffff’
  • represented in ASCII(256 or 2 power 8) or UTF-8 encodings (65535 or 2 power 16)
  • characters together forms a String
  • Array: char array – char[]

1

Note: when you type a character in a notepad and store it will be stored as 1 byte

  • ASCII character -> 1 byte – 8 bit
  • enter /return -> 2 bytes – 16 bit

Floating Point

  • stored in memory as exponents (8 bit) and mantissa (23 bit) and sign bit (1 bit)
  • float – 32 bit
  • double – 64 bit
  • Array: float array – float[]

1.pngInteger

  • short – 16 bit
  • int – 32 bit
  • long – 64 bit
  • Array: char array – int[]

1

Enumerated Types

  • These are fixed length strings

 

 

Integer Array

  • Check for null input array
    • passing null to the function call

findMid(null); // expecting valid array elements

check : if(array != null)

  • Check for validity of data type
    • passing improper data type to the function call

char[] ch = new char[10];

findMid(ch); //expecting an integer array

check: if(array instanceof int[])

  • Check for no valid elements
    • passing a valid integer array with no proper values for the function
    • This can be considered as one of the input and this check is debatable

int[] val = new int[10];

findMid(val); //expecting a valid input array of length 3

check: if(array.length > 3)

  • Check for single elements
    • passing an array with single element in it

int[] val = {1};

findMid(val); // expecting at least 3 elements

check: if(array.length > 3)

  • Check for all positive numbers
    • This is a positive testing with proper values for the array elements

int[] val = {1,2,3,4,5}

check: if(array[index] > 0)

  • Check for all negative numbers
    • pass negative numbers for the array inputs
    • your function should consider negative values also

int[] val = {-11,-12,-13,-4,-5}

check: if(array[index] < 0)

  • Check for duplicate elements
    • pass duplicates and see how the function responds
    • you function should handle duplicates

int[] val = {-11,-11,0,0,1,1}

check: if(array[index] != array[index+1]) // in sorted adjacent duplicates

  • Check for positive and negative number combinations
    • pass combinations of negative and positive values

int[] val = {-11,7,5,-13,0,1,21,-31}

  • Check for Minimum and Maximum overflow
    • pass value that is over the integer max or min value
    • your function should handle overflows

int[] val = {2147483647,65535 ,–2147483648,4294967295};

check: if(array[index] > Integer.MAX_VALUE)

if(array[index] < Integer.MIN_VALUE)

  • Check for Array Index Overflow
    • sometimes array index overflow arises if you are checking for a value that is referring to an invalid index in an array
    • your function should not result in array index overflow and you should handle it

for(int i =0;i<array.length;i++){

if(array[i] == array[i+1]) //array index overflow for array[i+1]

}

  • Check for ordering / non ordering
    • some times you might want to check if the array is sorted or not before processing further. in case of Binary Search in an array

Strings

  • Check for null input
    • passing null to the function call

check: if(str != null)

  • Check for “” for string as input
    • passing no value to the string

check: if(!str.equals(“”))

  • Check for single character
    • passing single character to the string

check: if(str.length > 3) //expecting minimum of 3 character in the input string

  • Check for case sensitivity
    • you will have to check for case sensitive for the function involving character manipulations

check: if(str.charAt(index) >= 65 && str.charAt(index) <= 90 ) // upper case

if(str.charAt(index) >= 97 && str.charAt(index) <= 122 ) // lower case

  • Check for digits
    • you will have to limit the characters to digits for integer calculations considering only 0 to 9

check: if(str.charAt(index) >= 48 && str.charAt(index) <= 57)

  • Check for special characters
    • you will have to consider only special characters at times in a function
    • some common special characters are space (32), comma (44), colon (58), semicolon (59) etc. for others you can look up the ASCII table and get the corresponding values

check: if(str.charAt(index) == 32 || str.charAt(index) == 44 || str.charAt(index) == 58 || str.charAt(index) == 59)

  • Check for duplicate characters
    • consider duplicate character presence consecutively.

check: if(str.charAt(index) == str.charAt(index + 1))

  • Check for ASCII or Unicode characters
  • process for ASCII or Unicode according to the need

check: if(str.getBytes( “UTF-8” ))

  • Check for index out of bound access
    • look for index out of bound when using charAt() function

Function

  • Check if the function returns a value
    • sometimes we tend to have a return statement which is inside an if clause but forget to add a default return statement
  • Check for base case of the problem first
    • some of the base case for the problem is to be added at the top of the function to by pass additional checks

These are some of the basic test cases to be considered for most of the functions that you write in java or any other languages

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Description:

This problem is same as that of Leetcode – 15 – 3Sum  but the change is that we have return the closest sum instead of the elements adding up to zero.

Solution (three pointers)

The approach that we are talking about is to sort the array first and then have one pointer running along the length of the array. We will have another two pointer to point to the start and end of the array elements

We will check for the sum store in a variable and if its equal to the target then we return the result. Otherwise we will get the difference and see if the value is closest enough to the target and return the closest after checking for all the elements in the array.

1

Code:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int leastDiff = Integer.MAX_VALUE;
        int closest = 0;
        if(nums != null && n >= 3){
            Arrays.sort(nums);
            for(int i=0;i < n-2;i++){
                for(int j = i+1, k = n-1;j<k;){
                    int result = nums[i] + nums[j] + nums[k];
                    if(result == target){
                        return result;  
                    }
                    else{
                        int diff = Math.abs(target - result);
                        if(diff < leastDiff){
                            leastDiff = diff;
                            closest = result;
                        }
                        if(result > target){
                          k--;  
                        }
                        else{
                         j++;   
                        }
                    }
                }
                }
            }
            return closest;
        }    
    }

Time Complexity: O(n2)

  • Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

  • We will adding 3 elements to the list and can have n number of combinations  – O(n)

Available Test Cases: 120

  • Check for empty array
  • Check for duplicate elements

Github:

Leetcode_16_3_Sum_Closest