Tag Archives: java generics

Programming Exercise – Binary Tree

Like sorting algorithms, binary tree implementation is another good programming exercise. In particular, methods for traversing a tree, searching nodes in a binary search tree and many other binary tree operations form a great recipe for refreshing one’s programming skills. Appended is an implementation of a pretty comprehensive set of binary tree (and binary search tree) operations in Java.

Iterative and recursive methods for each of the operations are developed and grouped in two separate classes, BinTreeI and BinTreeR. In general, most operations are easier to be implemented using recursive methods. For instance, calculating tree height using iterative method is a rather non-trivial exercise whereas it’s almost an one-liner using recursion. Some of the operations such as searching and inserting a tree node are only applicable to binary search tree (BST), for which in-order tree traversal should be used. For generality, pre-order and post-order traversal methods are also included in the code.

Similar to the implementation of sorting algorithms in a previous blog, Java Generics and Comparable interface are used. If wanted, the underlying tree node could be further expanded to contain more complex node data such as map entries (e.g. with class type <Key extends Comparable<Key>, Value>, and Map.Entry<K,V> data).

Node.java – binary tree node

package bintree;

class Node<E extends Comparable<E>> {
    public E element;
    public Node left;
    public Node right;

    public Node() {
        this(null);
    }

    public Node(E e) {
        element = e;
        left = null;
        right = null;
    }

    boolean isLeaf() {
        return (left == null && right == null);
    }

    public void printNode() {
        if (isLeaf())
            System.out.print(element + "* -> ");
        else
            System.out.print(element + " -> ");
    }
}

package bintree;

class Node<E extends Comparable<E>> {

public E element;

public Node left;

public Node right;

public Node() {

this(null);

}

public Node(E e) {

element = e;

left = null;

right = null;

}

boolean isLeaf() {

return (left == null && right == null);

}

public void printNode() {

if (isLeaf())

System.out.print(element + "* -> ");

else

System.out.print(element + " -> ");

}

BinTree.java – base binary tree class

package bintree;

import java.util.LinkedList;

// BinTree interface
@SuppressWarnings({"unchecked"})
abstract class BinTree<E extends Comparable<E>> {
    public Node root;

    public BinTree() {
        root = null;
    }

    public BinTree(E e) {
        root = new Node(e);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void addLeft(Node currNode, E e) {
        // CAUTION: this method overwrites left subtree, if exists
        currNode.left = new Node(e);
    }

    public void addRight(Node currNode, E e) {
        // CAUTION: this method overwrites right subtree, if exists
        currNode.right = new Node(e);
    }

    public void removeLeft(Node currNode) {
        if (currNode.left != null) {
            currNode.left = null;
        }
    }

    public void removeRight(Node currNode) {
        if (currNode.right != null) {
            currNode.right = null;
        }
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public abstract boolean search(Node currNode, E e);

    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public abstract void insert(Node currNode, E e);

    // Delete the first node found with matching data by replacing it with the
    // max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public abstract boolean deleteFirst(Node currNode, E e);

    public abstract int size(Node currNode);

    public abstract int height(Node currNode);

    public Node rotateLeft(Node currNode) {
        Node tempNode = currNode.right;
        currNode.right = tempNode.left;
        tempNode.left = currNode;
        return tempNode;  // New root node
    }

    public Node rotateRight(Node currNode) {
        Node tempNode = currNode.left;
        currNode.left = tempNode.right;
        tempNode.right = currNode;
        return tempNode;  // New root node
    }

    // In-order traversal
    public abstract void traverseIn(Node currNode);

    // Pre-order traversal
    public abstract void traversePre(Node currNode);

    // Post-order traversal
    public abstract void traversePost(Node currNode);

    public void printNodeEnd() {
        System.out.println("(end)");
    }
}

package bintree;

import java.util.LinkedList;

// BinTree interface

@SuppressWarnings({"unchecked"})

abstract class BinTree<E extends Comparable<E>> {

public Node root;

public BinTree() {

root = null;

}

public BinTree(E e) {

root = new Node(e);

}

public boolean isEmpty() {

return root == null;

}

public void addLeft(Node currNode, E e) {

// CAUTION: this method overwrites left subtree, if exists

currNode.left = new Node(e);

}

public void addRight(Node currNode, E e) {

// CAUTION: this method overwrites right subtree, if exists

currNode.right = new Node(e);

}

public void removeLeft(Node currNode) {

if (currNode.left != null) {

currNode.left = null;

}

public void removeRight(Node currNode) {

if (currNode.right != null) {

currNode.right = null;

}

// Search the subtree under the current node for matching data

// (Applicable to Binary Search Tree only)

public abstract boolean search(Node currNode, E e);

// Insert a node into the subtree under the current node

// (Applicable to Binary Search Tree only)

public abstract void insert(Node currNode, E e);

// Delete the first node found with matching data by replacing it with the

// max-value node in the branch to the left of the found node

// (Applicable to Binary Search Tree only)

public abstract boolean deleteFirst(Node currNode, E e);

public abstract int size(Node currNode);

public abstract int height(Node currNode);

public Node rotateLeft(Node currNode) {

Node tempNode = currNode.right;

currNode.right = tempNode.left;

tempNode.left = currNode;

return tempNode; // New root node

}

public Node rotateRight(Node currNode) {

Node tempNode = currNode.left;

currNode.left = tempNode.right;

tempNode.right = currNode;

return tempNode; // New root node

}

// In-order traversal

public abstract void traverseIn(Node currNode);

// Pre-order traversal

public abstract void traversePre(Node currNode);

// Post-order traversal

public abstract void traversePost(Node currNode);

public void printNodeEnd() {

System.out.println("(end)");

}

BinTreeR.java – binary tree class using recursive methods

package bintree;

import java.util.LinkedList;

// BinTree class using recursive methods
@SuppressWarnings({"unchecked"})
class BinTreeR<E extends Comparable<E>> extends BinTree<E> {
    public Node root;

    public BinTreeR() {
        super();
    }

    public BinTreeR(E e) {
        super(e);
    }

    public boolean isEmpty() {
        return super.isEmpty();
    }

    public void addLeft(Node currNode, E e) {
        super.addLeft(currNode, e);
    }

    public void addRight(Node currNode, E e) {
        super.addRight(currNode, e);
    }

    public void removeLeft(Node currNode) {
        super.removeLeft(currNode);
    }

    public void removeRight(Node currNode) {
        super.removeRight(currNode);
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public boolean search(Node currNode, E e) {
        if (currNode == null) {
            return false;
        }
        else {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0)
                    return search(currNode.left, e);            
                else
                    return search(currNode.right, e);         
            }
        }
    }

    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public void insert(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return;

        if (((Comparable) e).compareTo(currNode.element) <= 0) {
            if (currNode.left == null)
                currNode.left = new Node(e);
            else
                insert(currNode.left, e);            
        }
        else {
            if (currNode.right == null)
                currNode.right = new Node(e);
            else
                insert(currNode.right, e);            
        }
    }

    // Delete the first node found with matching data in the subtree under the current node
    // by replacing it with the max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public boolean deleteFirst(Node currNode, E e) {
        return deleteFirst(currNode, null, true, e);
    }

    // deleteFirst helper recursive method carrying parentNode
    public boolean deleteFirst(Node currNode, Node parentNode, boolean onLeft, E e) {
        if (currNode == null) {
            return false;
        }
        else {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                if (currNode.left == null) {
                    if (onLeft)
                        parentNode.left = currNode.right;
                    else
                        parentNode.right = currNode.right;
                }
                else if (currNode.right == null) {
                    if (onLeft)
                        parentNode.left = currNode.left;
                    else
                        parentNode.right = currNode.left;
                }
                else {
                    // currNode takes data of maxNode on currNode's left branch and remove maxNode
                    Node maxNode = currNode.left;
                    Node maxNodeParent = currNode;

                    if (maxNode.right == null) {
                        currNode.element = maxNode.element;
                        maxNodeParent.left = maxNode.left;
                    }
                    else {
                        while (maxNode.right != null) {
                            maxNodeParent = maxNode;
                            maxNode = maxNode.right;
                        }
                        currNode.element = maxNode.element;
                        maxNodeParent.right = null;
                    }
                }
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    onLeft = true;
                    return deleteFirst(currNode.left, currNode, onLeft, e);
                }
                else {
                    onLeft = false;
                    return deleteFirst(currNode.right, currNode, onLeft, e);
                }
            }
        }
    }

    public int size(Node currNode) {
        if (currNode == null)
            return 0;
        else
            return (size(currNode.left) + size(currNode.right) + 1);
    }

    public int height(Node currNode) {
        if (currNode == null)
            return -1;
        else
            return (Math.max(height(currNode.left), height(currNode.right)) + 1);
    }

    public Node rotateLeft(Node currNode) {
        return super.rotateLeft(currNode);
    }

    public Node rotateRight(Node currNode) {
        return super.rotateRight(currNode);
    }

    // In-order traversal (recursive)
    public void traverseIn(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            traverseIn(currNode.left);
            currNode.printNode();
            traverseIn(currNode.right);
        }
    }

    // Pre-order traversal (recursive)
    public void traversePre(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            currNode.printNode();
            traversePre(currNode.left);
            traversePre(currNode.right);
        }
    }

    // Post-order traversal (recursive)
    public void traversePost(Node currNode) {
        if(currNode == null) {
            return;
        }
        else {
            traversePost(currNode.left);
            traversePost(currNode.right);
            currNode.printNode();
        }
    }

    public void printNodeEnd() {
        super.printNodeEnd();
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

package bintree;

import java.util.LinkedList;

// BinTree class using recursive methods

@SuppressWarnings({"unchecked"})

class BinTreeR<E extends Comparable<E>> extends BinTree<E> {

public Node root;

public BinTreeR() {

super();

}

public BinTreeR(E e) {

super(e);

}

public boolean isEmpty() {

return super.isEmpty();

}

public void addLeft(Node currNode, E e) {

super.addLeft(currNode, e);

}

public void addRight(Node currNode, E e) {

super.addRight(currNode, e);

}

public void removeLeft(Node currNode) {

super.removeLeft(currNode);

}

public void removeRight(Node currNode) {

super.removeRight(currNode);

}

// Search the subtree under the current node for matching data

// (Applicable to Binary Search Tree only)

public boolean search(Node currNode, E e) {

if (currNode == null) {

return false;

}

else {

if (((Comparable) e).compareTo(currNode.element) == 0) {

return true;

}

else {

if (((Comparable) e).compareTo(currNode.element) < 0)

return search(currNode.left, e);

else

return search(currNode.right, e);

}

// Insert a node into the subtree under the current node

// (Applicable to Binary Search Tree only)

public void insert(Node currNode, E e) {

if (currNode == null) // Do nothing if the input node is null

return;

if (((Comparable) e).compareTo(currNode.element) <= 0) {

if (currNode.left == null)

currNode.left = new Node(e);

else

insert(currNode.left, e);

}

else {

if (currNode.right == null)

currNode.right = new Node(e);

else

insert(currNode.right, e);

}

// Delete the first node found with matching data in the subtree under the current node

// by replacing it with the max-value node in the branch to the left of the found node

// (Applicable to Binary Search Tree only)

public boolean deleteFirst(Node currNode, E e) {

return deleteFirst(currNode, null, true, e);

}

// deleteFirst helper recursive method carrying parentNode

public boolean deleteFirst(Node currNode, Node parentNode, boolean onLeft, E e) {

if (currNode == null) {

return false;

}

else {

if (((Comparable) e).compareTo(currNode.element) == 0) {

if (currNode.left == null) {

if (onLeft)

parentNode.left = currNode.right;

else

parentNode.right = currNode.right;

}

else if (currNode.right == null) {

if (onLeft)

parentNode.left = currNode.left;

else

parentNode.right = currNode.left;

}

else {

// currNode takes data of maxNode on currNode's left branch and remove maxNode

Node maxNode = currNode.left;

Node maxNodeParent = currNode;

if (maxNode.right == null) {

currNode.element = maxNode.element;

maxNodeParent.left = maxNode.left;

}

else {

while (maxNode.right != null) {

maxNodeParent = maxNode;

maxNode = maxNode.right;

}

currNode.element = maxNode.element;

maxNodeParent.right = null;

}

return true;

}

else {

if (((Comparable) e).compareTo(currNode.element) < 0) {

onLeft = true;

return deleteFirst(currNode.left, currNode, onLeft, e);

}

else {

onLeft = false;

return deleteFirst(currNode.right, currNode, onLeft, e);

}

public int size(Node currNode) {

if (currNode == null)

return 0;

else

return (size(currNode.left) + size(currNode.right) + 1);

}

public int height(Node currNode) {

if (currNode == null)

return -1;

else

return (Math.max(height(currNode.left), height(currNode.right)) + 1);

}

public Node rotateLeft(Node currNode) {

return super.rotateLeft(currNode);

}

public Node rotateRight(Node currNode) {

return super.rotateRight(currNode);

}

// In-order traversal (recursive)

public void traverseIn(Node currNode) {

if(currNode == null) {

return;

}

else {

traverseIn(currNode.left);

currNode.printNode();

traverseIn(currNode.right);

}

// Pre-order traversal (recursive)

public void traversePre(Node currNode) {

if(currNode == null) {

return;

}

else {

currNode.printNode();

traversePre(currNode.left);

traversePre(currNode.right);

}

// Post-order traversal (recursive)

public void traversePost(Node currNode) {

if(currNode == null) {

return;

}

else {

traversePost(currNode.left);

traversePost(currNode.right);

currNode.printNode();

}

public void printNodeEnd() {

super.printNodeEnd();

}

BinTreeI.java – binary tree class using iterative methods

package bintree;

import java.util.LinkedList;

// BinTree class using iterative methods
@SuppressWarnings({"unchecked"})
class BinTreeI<E extends Comparable<E>> extends BinTree<E> {
    public Node root;

    public BinTreeI() {
        super();
    }

    public BinTreeI(E e) {
        super(e);
    }

    public boolean isEmpty() {
        return super.isEmpty();
    }

    public void addLeft(Node currNode, E e) {
        super.addLeft(currNode, e);
    }

    public void addRight(Node currNode, E e) {
        super.addRight(currNode, e);
    }

    public void removeLeft(Node currNode) {
        super.removeLeft(currNode);
    }

    public void removeRight(Node currNode) {
        super.removeRight(currNode);
    }

    // Search the subtree under the current node for matching data
    // (Applicable to Binary Search Tree only)
    public boolean search(Node currNode, E e) {
        if (currNode == null)
            return false;

        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                return true;
            }
            else {
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    currNode = currNode.left;
                }
                else {
                    currNode = currNode.right;
                }
            }
        }
        return false;
    }
    // Insert a node into the subtree under the current node
    // (Applicable to Binary Search Tree only)
    public void insert(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return;

        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) <= 0) {
                if (currNode.left != null)
                    currNode = currNode.left;
                else {
                    currNode.left = new Node(e);
                    break;
                }
            }
            else {
                if (currNode.right != null)
                    currNode = currNode.right;
                else {
                    currNode.right = new Node(e);
                    break;
                }
            }
        }
    }

    // Delete the first node found with matching data in the subtree under the current node
    // by replacing it with the max-value node in the branch to the left of the found node
    // (Applicable to Binary Search Tree only)
    public boolean deleteFirst(Node currNode, E e) {
        if (currNode == null)  // Do nothing if the input node is null
            return false;

        boolean onLeft = true;
        Node parentNode = null;

        // Search for the first node with matching data
        while (currNode != null) {
            if (((Comparable) e).compareTo(currNode.element) == 0) {
                break;
            }
            else {
                parentNode = currNode;
                if (((Comparable) e).compareTo(currNode.element) < 0) {
                    onLeft = true;
                    currNode = currNode.left;
                }
                else {
                    onLeft = false;
                    currNode = currNode.right;
                }
            }
        }

        if (currNode == null) {  // No node with matching data
            return false;
        }
        else {
            if (currNode.left == null) {
                // Remove currNode
                if (onLeft)
                    parentNode.left = currNode.right;
                else
                    parentNode.right = currNode.right;
            }
            else if (currNode.right == null) {
                // Remove currNode
                if (onLeft)
                    parentNode.left = currNode.left;
                else
                    parentNode.right = currNode.left;
            }
            else {
                // currNode takes data of maxNode on currNode's left branch and remove maxNode
                Node maxNode = currNode.left;
                Node maxNodeParent = currNode;

                if (maxNode.right == null) {
                    currNode.element = maxNode.element;
                    maxNodeParent.left = maxNode.left;
                }
                else {
                    while (maxNode.right != null) {
                        maxNodeParent = maxNode;
                        maxNode = maxNode.right;
                    }
                    currNode.element = maxNode.element;
                    maxNodeParent.right = null;
                }
            }
        }
        return true;
    }

    // Calculate tree size using in-order traversal logic
    public int size(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        int nodeCount = 0;

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                nodeCount++;
                currNode = currNode.right;
            }
        }
        return nodeCount;
    }

    // Calculate tree height using post-order traversal logic
    public int height(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        Node prevNode = null;
        int maxCount = 0;

        if (currNode == null)
            return -1;
        stack.push(currNode);

        while (!stack.isEmpty()) {
            currNode = stack.peek();
            // Traversing down the tree from left or right
            if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {
                if (currNode.left != null)
                    stack.push(currNode.left);
                else if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the left
            else if (currNode.left == prevNode) {
                if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the right, at a leaf node or otherwise
            else {
                currNode = stack.pop();
            }
            prevNode = currNode;
            if (stack.size() > maxCount)
                maxCount = stack.size();
        }
        return maxCount - 1;
    }

    public Node rotateLeft(Node currNode) {
        return super.rotateLeft(currNode);
    }

    public Node rotateRight(Node currNode) {
        return super.rotateRight(currNode);
    }

    // In-order traversal
    public void traverseIn(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                currNode.printNode();
                currNode = currNode.right;
            }
        }
        printNodeEnd();
    }

    // Pre-order traversal
    public void traversePre(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();

        while (currNode != null || !stack.isEmpty()) {
            if (currNode != null) {
                stack.push(currNode);
                currNode.printNode();
                currNode = currNode.left;
            }
            else {
                currNode = stack.pop();
                currNode = currNode.right;
            }
        }
        printNodeEnd();
    }

    // Post-order traversal using a single stack
    public void traversePost(Node currNode) {
        LinkedList<Node> stack = new LinkedList<Node>();
        Node prevNode = null;

        if (currNode == null)
            return;
        stack.push(currNode);

        while (!stack.isEmpty()) {
            currNode = stack.peek();
            // Traversing down the tree from left or right
            if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {
                if (currNode.left != null)
                    stack.push(currNode.left);
                else if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the left
            else if (currNode.left == prevNode) {
                if (currNode.right != null)
                    stack.push(currNode.right);
            }
            // Traversing up the tree from the right or otherwise
            else {
                currNode.printNode();
                currNode = stack.pop();
            }
            prevNode = currNode;
        }
        printNodeEnd();
    }

    /*
    // Post-order traversal using two stacks
    public void traversePost(Node currNode) {
        LinkedList<Node> inStack = new LinkedList<Node>();
        LinkedList<Node> outStack = new LinkedList<Node>();

        if (currNode == null)
            return;
        inStack.push(currNode);

        while (!inStack.isEmpty()) {
            currNode = inStack.pop();
            outStack.push(currNode);
            if (currNode.left != null)
                inStack.push(currNode.left);
            if (currNode.right != null)
                inStack.push(currNode.right);
        }

        while (!outStack.isEmpty()) {
            currNode = outStack.pop();
            currNode.printNode();
        }
        printNodeEnd();
    }
    */

    public void printNodeEnd() {
        super.printNodeEnd();
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

package bintree;

import java.util.LinkedList;

// BinTree class using iterative methods

@SuppressWarnings({"unchecked"})

class BinTreeI<E extends Comparable<E>> extends BinTree<E> {

public Node root;

public BinTreeI() {

super();

}

public BinTreeI(E e) {

super(e);

}

public boolean isEmpty() {

return super.isEmpty();

}

public void addLeft(Node currNode, E e) {

super.addLeft(currNode, e);

}

public void addRight(Node currNode, E e) {

super.addRight(currNode, e);

}

public void removeLeft(Node currNode) {

super.removeLeft(currNode);

}

public void removeRight(Node currNode) {

super.removeRight(currNode);

}

// Search the subtree under the current node for matching data

// (Applicable to Binary Search Tree only)

public boolean search(Node currNode, E e) {

if (currNode == null)

return false;

while (currNode != null) {

if (((Comparable) e).compareTo(currNode.element) == 0) {

return true;

}

else {

if (((Comparable) e).compareTo(currNode.element) < 0) {

currNode = currNode.left;

}

else {

currNode = currNode.right;

}

return false;

}

// Insert a node into the subtree under the current node

// (Applicable to Binary Search Tree only)

public void insert(Node currNode, E e) {

if (currNode == null) // Do nothing if the input node is null

return;

while (currNode != null) {

if (((Comparable) e).compareTo(currNode.element) <= 0) {

if (currNode.left != null)

currNode = currNode.left;

else {

currNode.left = new Node(e);

break;

}

else {

if (currNode.right != null)

currNode = currNode.right;

else {

currNode.right = new Node(e);

break;

}

// Delete the first node found with matching data in the subtree under the current node

// by replacing it with the max-value node in the branch to the left of the found node

// (Applicable to Binary Search Tree only)

public boolean deleteFirst(Node currNode, E e) {

if (currNode == null) // Do nothing if the input node is null

return false;

boolean onLeft = true;

Node parentNode = null;

// Search for the first node with matching data

while (currNode != null) {

if (((Comparable) e).compareTo(currNode.element) == 0) {

break;

}

else {

parentNode = currNode;

if (((Comparable) e).compareTo(currNode.element) < 0) {

onLeft = true;

currNode = currNode.left;

}

else {

onLeft = false;

currNode = currNode.right;

}

if (currNode == null) { // No node with matching data

return false;

}

else {

if (currNode.left == null) {

// Remove currNode

if (onLeft)

parentNode.left = currNode.right;

else

parentNode.right = currNode.right;

}

else if (currNode.right == null) {

// Remove currNode

if (onLeft)

parentNode.left = currNode.left;

else

parentNode.right = currNode.left;

}

else {

// currNode takes data of maxNode on currNode's left branch and remove maxNode

Node maxNode = currNode.left;

Node maxNodeParent = currNode;

if (maxNode.right == null) {

currNode.element = maxNode.element;

maxNodeParent.left = maxNode.left;

}

else {

while (maxNode.right != null) {

maxNodeParent = maxNode;

maxNode = maxNode.right;

}

currNode.element = maxNode.element;

maxNodeParent.right = null;

}

return true;

}

// Calculate tree size using in-order traversal logic

public int size(Node currNode) {

LinkedList<Node> stack = new LinkedList<Node>();

int nodeCount = 0;

while (currNode != null || !stack.isEmpty()) {

if (currNode != null) {

stack.push(currNode);

currNode = currNode.left;

}

else {

currNode = stack.pop();

nodeCount++;

currNode = currNode.right;

}

return nodeCount;

}

// Calculate tree height using post-order traversal logic

public int height(Node currNode) {

LinkedList<Node> stack = new LinkedList<Node>();

Node prevNode = null;

int maxCount = 0;

if (currNode == null)

return -1;

stack.push(currNode);

while (!stack.isEmpty()) {

currNode = stack.peek();

// Traversing down the tree from left or right

if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {

if (currNode.left != null)

stack.push(currNode.left);

else if (currNode.right != null)

stack.push(currNode.right);

}

// Traversing up the tree from the left

else if (currNode.left == prevNode) {

if (currNode.right != null)

stack.push(currNode.right);

}

// Traversing up the tree from the right, at a leaf node or otherwise

else {

currNode = stack.pop();

}

prevNode = currNode;

if (stack.size() > maxCount)

maxCount = stack.size();

}

return maxCount - 1;

}

public Node rotateLeft(Node currNode) {

return super.rotateLeft(currNode);

}

public Node rotateRight(Node currNode) {

return super.rotateRight(currNode);

}

// In-order traversal

public void traverseIn(Node currNode) {

LinkedList<Node> stack = new LinkedList<Node>();

while (currNode != null || !stack.isEmpty()) {

if (currNode != null) {

stack.push(currNode);

currNode = currNode.left;

}

else {

currNode = stack.pop();

currNode.printNode();

currNode = currNode.right;

}

printNodeEnd();

}

// Pre-order traversal

public void traversePre(Node currNode) {

LinkedList<Node> stack = new LinkedList<Node>();

while (currNode != null || !stack.isEmpty()) {

if (currNode != null) {

stack.push(currNode);

currNode.printNode();

currNode = currNode.left;

}

else {

currNode = stack.pop();

currNode = currNode.right;

}

printNodeEnd();

}

// Post-order traversal using a single stack

public void traversePost(Node currNode) {

LinkedList<Node> stack = new LinkedList<Node>();

Node prevNode = null;

if (currNode == null)

return;

stack.push(currNode);

while (!stack.isEmpty()) {

currNode = stack.peek();

// Traversing down the tree from left or right

if (prevNode == null || currNode == prevNode.left || currNode == prevNode.right) {

if (currNode.left != null)

stack.push(currNode.left);

else if (currNode.right != null)

stack.push(currNode.right);

}

// Traversing up the tree from the left

else if (currNode.left == prevNode) {

if (currNode.right != null)

stack.push(currNode.right);

}

// Traversing up the tree from the right or otherwise

else {

currNode.printNode();

currNode = stack.pop();

}

prevNode = currNode;

}

printNodeEnd();

}

// Post-order traversal using two stacks

public void traversePost(Node currNode) {

LinkedList<Node> inStack = new LinkedList<Node>();

LinkedList<Node> outStack = new LinkedList<Node>();

if (currNode == null)

return;

inStack.push(currNode);

while (!inStack.isEmpty()) {

currNode = inStack.pop();

outStack.push(currNode);

if (currNode.left != null)

inStack.push(currNode.left);

if (currNode.right != null)

inStack.push(currNode.right);

}

while (!outStack.isEmpty()) {

currNode = outStack.pop();

currNode.printNode();

}

printNodeEnd();

}

public void printNodeEnd() {

super.printNodeEnd();

}

BinTreeMain.java – test application

package bintree;

import java.io.*;
import java.util.*;

class BinTreeMain {

    @SuppressWarnings({"unchecked"})
    public static void main(String[] args) {
        if (args.length != 1 || !args[0].matches("[iIrR]")) {
            System.out.println("Usage: java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain I|R (Iterative or Recursive)");
            System.out.println("  e.g. java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain R");
            System.exit(0);
        }

        BinTree tree = null;

        boolean useRecurMethods = args[0].matches("[rR]");
        if (!useRecurMethods) {
            tree = new BinTreeI();
        }
        else {
            tree = new BinTreeR();
        }

        /* Tree content

                      (E)
                     /   \
                   /       \
                (C)         (H)
               /   \       /   \
            (B)    (D)  (G)     (J)
           /           /       /
        (A)         (F)     (I)
                           /   \
                       (HH)     (II)

        */

        tree.root = new Node("E");

        // Test insert
        tree.insert(tree.root, "H");
        tree.insert(tree.root, "C");
        tree.insert(tree.root, "D");
        tree.insert(tree.root, "G");
        tree.insert(tree.root, "B");
        tree.insert(tree.root, "J");
        tree.insert(tree.root, "F");
        tree.insert(tree.root, "A");
        tree.insert(tree.root, "I");
        tree.insert(tree.root, "HH");
        tree.insert(tree.root, "II");

        // Test search
        System.out.println("Result: " + (tree.search(tree.root, "G") ? "Found!" : "Not found!"));
        System.out.println("Result: " + (tree.search(tree.root, "FF") ? "Found!" : "Not found!"));

        System.out.println("\nTraversing tree from root ...");
        tree.traverseIn(tree.root);
        if (useRecurMethods) tree.printNodeEnd();
        System.out.println("\nSize of tree: " + tree.size(tree.root));
        System.out.println("Height of tree: " + tree.height(tree.root));

        // Test delete
        System.out.println("\nDeleting first node containing B from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "B") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing CC from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "CC") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing H from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "H") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing J from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "J") ? "Found and deleted!" : "Not found!"));

        System.out.println("\nDeleting first node containing E (root node) from root ...");
        System.out.println("Result: " + (tree.deleteFirst(tree.root, "E") ? "Found and deleted!" : "Not found!"));
        System.out.println("Root node now has data " + tree.root.element);

        System.out.println("\nTraversing tree from root ...");
        tree.traverseIn(tree.root);
        if (useRecurMethods) tree.printNodeEnd();
        System.out.println("\nSize of tree: " + tree.size(tree.root));
        System.out.println("Height of tree: " + tree.height(tree.root));
    }
}

package bintree;

import java.io.*;

import java.util.*;

class BinTreeMain {

@SuppressWarnings({"unchecked"})

public static void main(String[] args) {

if (args.length != 1 || !args[0].matches("[iIrR]")) {

System.out.println("Usage: java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain I|R (Iterative or Recursive)");

System.out.println(" e.g. java -cp build/bintree-r1.0.0.jar bintree.BinTreeMain R");

System.exit(0);

}

BinTree tree = null;

boolean useRecurMethods = args[0].matches("[rR]");

if (!useRecurMethods) {

tree = new BinTreeI();

}

else {

tree = new BinTreeR();

}

/* Tree content

(E)

/ \

/ \ / \

(B) (D) (G) (J)

/ / /

(A) (F) (I)

/ \

(HH) (II)

tree.root = new Node("E");

// Test insert

tree.insert(tree.root, "H");

tree.insert(tree.root, "C");

tree.insert(tree.root, "D");

tree.insert(tree.root, "G");

tree.insert(tree.root, "B");

tree.insert(tree.root, "J");

tree.insert(tree.root, "F");

tree.insert(tree.root, "A");

tree.insert(tree.root, "I");

tree.insert(tree.root, "HH");

tree.insert(tree.root, "II");

// Test search

System.out.println("Result: " + (tree.search(tree.root, "G") ? "Found!" : "Not found!"));

System.out.println("Result: " + (tree.search(tree.root, "FF") ? "Found!" : "Not found!"));

System.out.println("\nTraversing tree from root ...");

tree.traverseIn(tree.root);

if (useRecurMethods) tree.printNodeEnd();

System.out.println("\nSize of tree: " + tree.size(tree.root));

System.out.println("Height of tree: " + tree.height(tree.root));

// Test delete

System.out.println("\nDeleting first node containing B from root ...");

System.out.println("Result: " + (tree.deleteFirst(tree.root, "B") ? "Found and deleted!" : "Not found!"));

System.out.println("\nDeleting first node containing CC from root ...");

System.out.println("Result: " + (tree.deleteFirst(tree.root, "CC") ? "Found and deleted!" : "Not found!"));

System.out.println("\nDeleting first node containing H from root ...");

System.out.println("Result: " + (tree.deleteFirst(tree.root, "H") ? "Found and deleted!" : "Not found!"));

System.out.println("\nDeleting first node containing J from root ...");

System.out.println("Result: " + (tree.deleteFirst(tree.root, "J") ? "Found and deleted!" : "Not found!"));

System.out.println("\nDeleting first node containing E (root node) from root ...");

System.out.println("Result: " + (tree.deleteFirst(tree.root, "E") ? "Found and deleted!" : "Not found!"));

System.out.println("Root node now has data " + tree.root.element);

System.out.println("\nTraversing tree from root ...");

tree.traverseIn(tree.root);

if (useRecurMethods) tree.printNodeEnd();

System.out.println("\nSize of tree: " + tree.size(tree.root));

System.out.println("Height of tree: " + tree.height(tree.root));

}

Programming Exercise – Sorting Algorithm

1 Reply

Unless algorithm development is part of the job, many software engineers use readily available algorithmic methods as needed and rarely need to develop algorithms themselves. I’m not talking about some complicated statistical or machine learning algorithms. Just simple mundane ones such as a sorting algorithm. Even if you don’t need to code algorithms, going back to writing a sorting program can still be a good exercise to review certain basic skills that might not be frequently used in your current day job. It’s a good-sized programming exercise that isn’t too trivial or taking up too much time. It also reminds you some clever (or dumb) tricks on how to perform sorting by means of recursive divide-and-merge, pivot partitioning, etc. And if nothing else, it might help you in your next technical job interview in the near future.

If you’re up for such an exercise, first, look up from Wikipedia or any other suitable source for a sorting algorithm (e.g. Merge Sort, Quick Sort) of your choice to re-familiarize yourself with its underlying mechanism. Next, decide on the scope of the application – for example, do you want an integer-sorting application or something more generic? … etc. Next, pseudo code, pick the programming language of your choice, and go for it.

Appended is a simple implementation of both Merge Sort and Quick Sort in Java. For the convenience of making method calls with varying data types and sorting algorithms, an interface (SimpleSort) and a wrapper (Sorter) are used. Java Generics is used to generalize the sorter for different data types. Adding Generics to a sorting application requires the using of either the Comparable or Comparator interface, as ordering is necessary in sorting. In this example application, the Comparable interface is used since the default ordering is good enough for basic sorting. The overall implementation code is pretty self explanatory.

SimpleSort.java

package sorting;

public interface SimpleSort<E extends Comparable<E>> {

    public void sort(E[] list);
}

package sorting;

public interface SimpleSort<E extends Comparable<E>> {

public void sort(E[] list);

}

Sorter.java

package sorting;

public class Sorter<E extends Comparable<E>> {

    public void performSorting(E[] list, SimpleSort<E> sortingAlgo) {
        long startTime, elapsedTime;

        System.out.println("\nOriginal " + list.getClass().getSimpleName() + " list:  ...");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + "  ");
        }
        System.out.println();

        startTime = System.currentTimeMillis();
        sortingAlgo.sort(list);
        elapsedTime = System.currentTimeMillis() - startTime;

        System.out.println("\nResult: " + sortingAlgo.getClass().getSimpleName() + " ...");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + "  ");
        }
        System.out.println("\n\nTime taken: " + elapsedTime + "ms");
    }
}

package sorting;

public class Sorter<E extends Comparable<E>> {

public void performSorting(E[] list, SimpleSort<E> sortingAlgo) {

long startTime, elapsedTime;

System.out.println("\nOriginal " + list.getClass().getSimpleName() + " list: ...");

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

System.out.print(list[i] + " ");

}

System.out.println();

startTime = System.currentTimeMillis();

sortingAlgo.sort(list);

elapsedTime = System.currentTimeMillis() - startTime;

System.out.println("\nResult: " + sortingAlgo.getClass().getSimpleName() + " ...");

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

System.out.print(list[i] + " ");

}

System.out.println("\n\nTime taken: " + elapsedTime + "ms");

}

MergeSort.java

package sorting;

public class MergeSort<E extends Comparable<E>> implements SimpleSort<E> {

    private E[] list;
    private E[] holder;

    @SuppressWarnings({"unchecked"})
    public void sort(E[] list) {
        this.list = list;
        int size = list.length;
        // Type erasure: first bound class of <E extends Comparable<E>>
        holder = (E[]) new Comparable[size];

        mergeSort(0, size - 1);
    }

    private void mergeSort(int left, int right) {
        if (left < right) {
            int center = left + (right - left) / 2;
            mergeSort(left, center);
            mergeSort(center + 1, right);
            merge(left, center, right);
        }
    }

    private void merge(int left, int center, int right) {

        for (int i = left; i <= right; i++) {
            holder[i] = list[i];
        }

        int i = left;
        int j = center + 1;
        int k = left;

        while (i <= center && j <= right) {

            if (holder[i].compareTo(holder[j]) <= 0) {
                list[k] = holder[i];  // Overwrite list[k] with element from the left list
                i++;
            }
            else {
                list[k] = holder[j];  // Overwrite list[k] with element from the right list
                j++;
            }
            k++;
        }

        // Overwirte remaining list[k] if the left list isn't exhausted
        // No need to do the same for the right list, as its elements are already correctly placed
        while (i <= center) {
            list[k] = holder[i];
            k++;
            i++;
        }
    }
}

package sorting;

public class MergeSort<E extends Comparable<E>> implements SimpleSort<E> {

private E[] list;

private E[] holder;

@SuppressWarnings({"unchecked"})

public void sort(E[] list) {

this.list = list;

int size = list.length;

// Type erasure: first bound class of <E extends Comparable<E>>

holder = (E[]) new Comparable[size];

mergeSort(0, size - 1);

}

private void mergeSort(int left, int right) {

if (left < right) {

int center = left + (right - left) / 2;

mergeSort(left, center);

mergeSort(center + 1, right);

merge(left, center, right);

}

private void merge(int left, int center, int right) {

for (int i = left; i <= right; i++) {

holder[i] = list[i];

}

int i = left;

int j = center + 1;

int k = left;

while (i <= center && j <= right) {

if (holder[i].compareTo(holder[j]) <= 0) {

list[k] = holder[i]; // Overwrite list[k] with element from the left list

i++;

}

else {

list[k] = holder[j]; // Overwrite list[k] with element from the right list

j++;

}

k++;

}

// Overwirte remaining list[k] if the left list isn't exhausted

// No need to do the same for the right list, as its elements are already correctly placed

while (i <= center) {

list[k] = holder[i];

k++;

i++;

}

QuickSort.java

package sorting;

import java.util.Random;

public class QuickSort<E extends Comparable<E>> implements SimpleSort<E> {

    private E[] list;

    @SuppressWarnings({"unchecked"})
    public void sort(E[] list) {
        this.list = list;
        int size = list.length;

        quickSort(list, 0, size-1);
    }

    private void swapListElements(E[] list, int index1, int index2) {
        E tempValue = list[index1];
        list[index1] = list[index2];
        list[index2] = tempValue;
    }

    private int partitionIndex(E[] list, int left, int right, int pivot) {
        int pivotIndex;
        E pivotValue;

        pivotValue = list[pivot];
        swapListElements(list, pivot, right);  // Swap pivot element to rightmost index

        pivotIndex = left;  // Calculate pivot index starting from leftmost index
        for (int i = left; i < right; i++) {
            if (list[i].compareTo(pivotValue) < 0) {
                swapListElements(list, i, pivotIndex);
                pivotIndex++;
            }
        }
        swapListElements(list, pivotIndex, right);  // Swap pivot element back to calculated pivot index

        return pivotIndex;
    }

    private void quickSort(E[] list, int left, int right) {
        int randomIndex, pivotIndex;

        if (left < right) {
            // Pick random index between left and right (inclusive)
            Random randomNum = new Random();
            randomIndex = randomNum.nextInt(right-left+1) + left;

            pivotIndex = partitionIndex(list, left, right, randomIndex);
            quickSort(list, left, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, right);
        }
        else
            return;
    }
}

package sorting;

import java.util.Random;

public class QuickSort<E extends Comparable<E>> implements SimpleSort<E> {

private E[] list;

@SuppressWarnings({"unchecked"})

public void sort(E[] list) {

this.list = list;

int size = list.length;

quickSort(list, 0, size-1);

}

private void swapListElements(E[] list, int index1, int index2) {

E tempValue = list[index1];

list[index1] = list[index2];

list[index2] = tempValue;

}

private int partitionIndex(E[] list, int left, int right, int pivot) {

int pivotIndex;

E pivotValue;

pivotValue = list[pivot];

swapListElements(list, pivot, right); // Swap pivot element to rightmost index

pivotIndex = left; // Calculate pivot index starting from leftmost index

for (int i = left; i < right; i++) {

if (list[i].compareTo(pivotValue) < 0) {

swapListElements(list, i, pivotIndex);

pivotIndex++;

}

swapListElements(list, pivotIndex, right); // Swap pivot element back to calculated pivot index

return pivotIndex;

}

private void quickSort(E[] list, int left, int right) {

int randomIndex, pivotIndex;

if (left < right) {

// Pick random index between left and right (inclusive)

Random randomNum = new Random();

randomIndex = randomNum.nextInt(right-left+1) + left;

pivotIndex = partitionIndex(list, left, right, randomIndex);

quickSort(list, left, pivotIndex - 1);

quickSort(list, pivotIndex + 1, right);

}

else

return;

}

SortingMain.java

package sorting;

public class SortingMain {

    @SuppressWarnings({"unchecked"})
    public static void main(String[] args) {

        Integer[] integerList = {8, 15, 6, 2, 11, 4, 7, 12, 3};
        Double[]  doubleList = {2.5, 8.0, 7.2, 4.9, 6.6, 1.8, 3.0, 7.5};
        Character[] characterList = {'M', 'X', 'B', 'C', 'T', 'R', 'F', 'S'};
        String[] stringList = {"lion", "tiger", "snow leopard", "jaguar", "cheeta", "cougar", "leopard"};

        Sorter sorter = new Sorter();

        sorter.performSorting(integerList, new MergeSort());
        sorter.performSorting(doubleList, new QuickSort());
        sorter.performSorting(characterList, new MergeSort());
        sorter.performSorting(stringList, new QuickSort());
    }
}

package sorting;

public class SortingMain {

@SuppressWarnings({"unchecked"})

public static void main(String[] args) {

Integer[] integerList = {8, 15, 6, 2, 11, 4, 7, 12, 3};

Double[] doubleList = {2.5, 8.0, 7.2, 4.9, 6.6, 1.8, 3.0, 7.5};

Character[] characterList = {'M', 'X', 'B', 'C', 'T', 'R', 'F', 'S'};

String[] stringList = {"lion", "tiger", "snow leopard", "jaguar", "cheeta", "cougar", "leopard"};

Sorter sorter = new Sorter();

sorter.performSorting(integerList, new MergeSort());

sorter.performSorting(doubleList, new QuickSort());

sorter.performSorting(characterList, new MergeSort());

sorter.performSorting(stringList, new QuickSort());

}

Genuine Blog

A Tech Blog by Leo Cheung

Tag Archives: java generics

Programming Exercise – Binary Tree

Programming Exercise – Sorting Algorithm