Why Hashtable doesn't allow null key/value while Hashmap does.

Why Hashtable doesn't allow null key/value while Hashmap does.


In this post we will learn why Hashtable doesn't allow null key and null value while HashMap does.

How Hashtable and HashMap compute bucket Index.

Before checking this post, I would recommend understanding how HashMap and Hashtable works here


Hashtable and HashMap both uses the given key to compute the bucket index, if the given key is null how will the bucket index be calculated. Also, key can be object and equality of which is determined by calling hashcode and equals on that object, so if the key is null that contract is not fulfilled.

So to summarize, Hashtable doesn't allow null key to compute the bucket index. 

HashMap is newer where it has corrected the issues in Hashtable and allows one null key and value. 
HashMap handles the null key as a special case and it has reserved the index "0" for the null key-value.


Sample Program.

package javabypatel.misc;

import java.util.HashMap;
import java.util.Hashtable;

public class Test {
	public static void main(String[] args) {
		Hashtable<String, String> hashtable = new Hashtable<>();
		//hashtable.put(null, "null"); // throws NPE
		//hashtable.put(null, "null"); // throws NPE

		HashMap<String, String> hashmap = new HashMap<>();
		hashmap.put(null, null);        // No problem
		hashmap.put(null, "my-value");  // No problem

		System.out.println(hashmap.get(null)); // Return value
	}
}


Create Linked Lists of all the nodes at each depth in a binary tree.

Create Linked Lists of all the nodes at each depth in a binary tree.


Creating linked list of Nodes at same level in a Binary tree is same as printing nodes at each level of a Binary tree with only difference is to collect the Nodes in a list for each level instead of printing it.   
 
Consider a below Binary Tree,

         50
       /    \
      /      \
     30       70
   /   \     /  \
  20   40   60  80
 /  \
10  25

Output:
50
30 -> 70
20 -> 40 -> 60 -> 80
10 -> 25


Create Linked Lists of all the nodes at each depth in a binary tree.

Take 2 queues, one for current level and one for next level.

Put the root node in current level and as we work on current level, we will put left and right child into next level queue as that will be the next level we will be working on.

Once we finish the current level queue, that is where our next level queue is ready to process if it is not empty that would be the case for last level which doesn't has any left/right child.

we initialize currentLevel to nextLevel and repeat the steps.


Create Linked Lists of all the nodes at each depth in a binary tree in Java.

package javabypatel.bt;

import java.util.*;

public class LinkedListAtEachDepthOfBinaryTree {
    public static void main(String[] args) {
        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

        List<LinkedList<Node>> linkedLists = createLinkedListOfNodesAtEachLevel(rootNode);
    }

    private static List<LinkedList<Node>> createLinkedListOfNodesAtEachLevel(Node root) {
        if (root == null)
            return null;

        List<LinkedList<Node>> linkedLists = new LinkedList<>();

        Queue<Node> currentLevel = new LinkedList<>();
        currentLevel.add(root);
        linkedLists.add(new LinkedList<>());

        Queue<Node> nextLevel = new LinkedList<>();

        while (!currentLevel.isEmpty()) {
            Node node = currentLevel.poll();
            linkedLists.get(linkedLists.size() - 1).add(node);
            System.out.print(node.getData() + ",");

            if (node.getLeft() != null)
                nextLevel.add(node.getLeft());

            if (node.getRight() != null)
                nextLevel.add(node.getRight());

            if (currentLevel.isEmpty() && !nextLevel.isEmpty()) {
                currentLevel = nextLevel;
                nextLevel = new LinkedList<>();
                linkedLists.add(new LinkedList<>());
                System.out.println();
            }
        }
        return linkedLists;
    }

    private static Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);

            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}
 
package javabypatel.bst;

public class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}


Find Inorder successor of a Node in BST

Find Inorder successor of a Node in BST.


Inorder traversal of a Binary Tree reads a Left most element first then a middle or root element and at last the right most element, so when we say successor of a Node, you have to return the next element of the Node in Inorder traversal.
 
Consider a below BST,

         50
       /    \
      /      \
     30       70
   /   \     /  \
  20   40   60  80
 /  \
10  25

Example:
Inorder Successor of Node 50 is 60
Inorder Successor of Node 25 is 30
Inorder Successor of Node 40 is 50
Inorder Successor of Node 80 is null
Inorder Successor of Node 70 is 80
  

Inorder traversal of a Binary Search Tree always return the data in sorted order. So one way to find is to do a Inorder traversal which would be 

10 20 25 30 40 50 60 70 80

and then you can sequentially search for the next element of the given node which is Inorder successor of a Node. this approach would have O(n) time and space complexity. lets optimize it to O(h) where h is height of tree. (Note: in case of skewed tree it will still be O(n)) 

Inorder Successor In BST

There are 2 case in finding Inorder successor of a Node in BST.

  • Given Node has Right Subtree
  • Given Node doesn't has right subtree

Given Node has Right Subtree, 


In this case, Node 50 has right subtree so the next element would obviously be the left most element in the right sub tree as that how Inorder traversal goes.

Given Node doesn't has right subtree,

In this case (Node 22), where there is no right sub tree, so the next element that is read in inorder successor is the root node 25 and the root node will always encountered when you visit left of any node (this is what is in-order traversal you first visit left most node, so if there is a node and it has left node, you will first visit that and then the root node.)

In above tree, we visited left side 3 times, one from Node 50, one from Node 30 and one from Node 25, so the last left taken is the answer which in this case is 25.

Consider Node 40, the last left you will take is only from Node 50, so Inorder successor of 40 is Node 50.

Inorder successor of Binary Search Tree in Java.

package javabypatel.bst;

public class InOrderSuccessor {
    public static void main(String[] args) {
        new InOrderSuccessor();
    }

    public InOrderSuccessor() {
        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

        System.out.println(inorderSuccessor(rootNode, 70, null).getData());
    }

    private Node inorderSuccessor(Node root, int k, Node lastLeftNodeVisited) {
        if (root == null) {
            return root;
        }

        if (root.getData() == k) {
            if (root.getRight() != null) {
                return findSmallestInLeft(root.getRight());
            } else {
                return lastLeftNodeVisited;
            }
        }

        if (k < root.getData()) {
            return inorderSuccessor(root.getLeft(), k, root);
        } else {
            return inorderSuccessor(root.getRight(), k, lastLeftNodeVisited);
        }
    }

    private Node findSmallestInLeft(Node root) {
        if (root == null || root.getLeft() == null) {
            return root;
        }

        return findSmallestInLeft(root.getLeft());
    }

    private Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);

            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}
 
package javabypatel.bst;

public class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}