Level Order Traversal of Binary Search Tree
Level order traversal of a binary search tree involves traversing the tree level by level, storing each level's nodes in a queue, and then performing dequeue (removing the node) and enqueue (storing the next level's nodes) operations to achieve the traversal.
Supporting level order traversal with a queue:
- If the root node is null, there is nothing to traverse.
- If the root node is not null:
- Enqueue the root node first.
- As long as the queue is not empty:
- Dequeue the front node and traverse it.
- If the front node has a left child, enqueue the left child.
- If the front node has a right child, enqueue the right child.
The following steps demonstrate this process:
(1) Enqueue the root node.
(2) Dequeue 29, and enqueue its left and right child nodes.
(3) Dequeue 17, and enqueue its child nodes 14 and 23.
(4) Dequeue 31, and enqueue its child nodes 30 and 43.
(5) Finally, dequeue all remaining nodes.
// Level order traversal of binary search tree
public void levelOrder(){
// We use LinkedList as our queue
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
Java Example Code
Source Code Download: Download
src/tutorialpro/binary/LevelTraverse.java File Code:
package tutorialpro.binary;
import java.util.LinkedList;
/**
* Level order traversal
*/
public class LevelTraverse<Key extends Comparable<Key>, Value>{
// Nodes in the tree are private classes, external parties do not need to know the specific implementation of binary search tree nodes
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
}
private Node root; // Root node
private int count; // Number of nodes in the tree
// Constructor, default to an empty binary search tree
public LevelTraverse() {
root = null;
count = 0;
}
// Returns the number of nodes in the binary search tree
public int size() {
return count;
}
// Returns whether the binary search tree is empty
public boolean isEmpty() {
return count == 0;
}
// Inserts a new (key, value) data pair into the binary search tree
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Checks if the binary search tree contains the key
public boolean contain(Key key){
return contain(root, key);
}
// Searches for the value corresponding to the key in the binary search tree. If it does not exist, returns null
public Value search(Key key){
return search( root , key );
}
// Pre-order traversal of the binary search tree
public void preOrder(){
preOrder(root);
}
// In-order traversal of the binary search tree
public void inOrder(){
inOrder(root);
}
// Post-order traversal of the binary search tree
public void postOrder(){
postOrder(root);
}
// Private methods to support the above operations
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else
node.right = insert( node.right, key, value);
return node;
}
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else
return contain( node.right , key );
}
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else
return search( node.right, key );
}
}
public void preOrder() {
preOrder(root);
}
// In-order traversal of the binary search tree
public void inOrder() {
inOrder(root);
}
// Post-order traversal of the binary search tree
public void postOrder() {
postOrder(root);
}
// Level-order traversal of the binary search tree
public void levelOrder() {
// We use LinkedList as our queue
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while (!q.isEmpty()) {
Node node = q.remove();
System.out.println(node.key);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
}
//********************
//* Helper functions for the binary search tree
//********************
// Insert a node (key, value) into the binary search tree rooted at node using a recursive algorithm
// Return the root of the binary search tree after inserting the new node
private Node insert(Node node, Key key, Value value) {
if (node == null) {
count++;
return new Node(key, value);
}
if (key.compareTo(node.key) == 0)
node.value = value;
else if (key.compareTo(node.key) < 0)
node.left = insert(node.left, key, value);
else // key > node.key
node.right = insert(node.right, key, value);
return node;
}
// Check if the binary search tree rooted at node contains a node with key using a recursive algorithm
private boolean contain(Node node, Key key) {
if (node == null)
return false;
if (key.compareTo(node.key) == 0)
return true;
else if (key.compareTo(node.key) < 0)
return contain(node.left, key);
else // key > node.key
return contain(node.right, key);
}
// Search for the value corresponding to key in the binary search tree rooted at node using a recursive algorithm
// Return null if the value does not exist
private Value search(Node node, Key key) {
if (node == null)
return null;
if (key.compareTo(node.key) == 0)
return node.value;
else if (key.compareTo(node.key) < 0)
return search(node.left, key);
else // key > node.key
return search(node.right, key);
}
// Pre-order traversal of the binary search tree rooted at node using a recursive algorithm
private void preOrder(Node node) {
if (node != null) {
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Recursive algorithm for in-order traversal of a binary search tree rooted at node
private void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Recursive algorithm for post-order traversal of a binary search tree rooted at node
private void postOrder(Node node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}