Objective: The objective of this lab is to help the students have a better under
ID: 3739322 • Letter: O
Question
Objective: The objective of this lab is to help the students have a better understanding of the reference based implementation of a Binary tree. The LAB will go back to a common node structure with each node only has two references refers to the left child and right child (no direct reference to its parent). This will help the students better adjust their learning to popular interview questions they may have to deal with in their future interviews. The LAB provides a simpler implementation for the linked binary tree discussed in class but slightly different (the size variable is removed from the binary tree class, the parent reference variable for each node has also been removed).
1. Create a project and put/copy all files in the simple binary tree folder and paste into the src folder. Remark: the size variable and parent reference have already been removed. You are recommended to read the provided code first, to figure out what is already available.
2. Due to the changes, the original implementation of the following methods will no longer work. Please based on this change, make necessary changes to the following methods
a) public int size() //return the number of nodes
b) public Node<E> parent(Node<E> p) throws IllegalArgumentException //return the parent node for a node referred by p
3. Add and implement the following methods within the class:
c) public boolean isIdentical(Node<E> p1, Node<E> p2): check if two binary trees rooted at p1 and p2 are identical or not. i.e. if they have identical structure & their contents are also same. Return true for yes and false, otherwise.http://www.techiedelight.com/check-if-two-binary-tree-are-identical-not-iterative-recursive/
d) public ArrayList<Node<E>> ancestors(Node<E>p1, Node<E> p2): find all ancestors of a given node referred by p2 on a tree rooted at p1.
for example, consider below binary tree: http://www.techiedelight.com/find-ancestors-of-given-node-binary-tree//
e) (Bonus) public Node<E> findLCA(Node<E> p1, Node<E> p2): find lowest common ancestor (LCA) of p1 and p2 in it.
http://www.techiedelight.com/find-lowest-common-ancestor-Ica-two-nodes-binary-tree/
Remark:
If you want to add extra methods to support the implementation of the required methods, please put them also at the end of the file for clarity.
The method definition can be different (such as return type or parameter list) as long as the objectives are the same.
Node.java:
package simpleBinaryTree;
public class Node<E extends Comparable<E>> {
private E element; // an element stored at this node
private Node<E> left; // a reference to the left child (if any)
private Node<E> right; // a reference to the right child (if any)
/**
* Constructs a node with the given element and neighbors.
*
* @param e the element to be stored
* @param leftChild reference to a left child node
* @param rightChild reference to a right child node
*/
public Node(E e, Node<E> leftChild, Node<E> rightChild) {
element = e;
left = leftChild;
right = rightChild;
}
// accessor methods
public E getElement() { return element; }
public Node<E> getLeft() { return left; }
public Node<E> getRight() { return right; }
// update methods
public void setElement(E e) { element = e; }
public void setLeft(Node<E> leftChild) { left = leftChild; }
public void setRight(Node<E> rightChild) { right = rightChild; }
}
SimpleLinkedBinaryTree.java:
package simpleBinaryTree;
import java.util.ArrayList;
public class simpleLinkedBinaryTree<E extends Comparable<E>> {
protected Node<E> root = null; // root of the tree
public simpleLinkedBinaryTree() { }//constructor_Construts an empty binary tree.
// Returns the root of the tree (or null if tree is empty).
public Node<E> root() {
return root;
}
public boolean isEmpty() { return root == null; }
public int numChildren(Node<E> p) {
int count=0;
if(p.getLeft()!=null) count++;
if(p.getRight()!=null) count++;
return count;
}
public ArrayList<Node<E>> children(Node<E> p) {
ArrayList<Node<E>> snapshot = new ArrayList<>(2); // max capacity of 2
if (left(p) != null)
snapshot.add(left(p));
if (right(p) != null)
snapshot.add(right(p));
return snapshot;
}
public boolean isInternal(Node<E> p) { return numChildren(p) > 0; }
public boolean isExternal(Node<E> p) { return numChildren(p) == 0; }
public Node<E> left(Node<E> p) throws IllegalArgumentException {
return p.getLeft();
}
public Node<E> right(Node<E> p) throws IllegalArgumentException {
return p.getRight();
}
// update methods supported by this class
/**
* Places element e at the root of an empty tree and returns its new Position.
*
* @param e the new element
* @return the Position of the new element
* @throws IllegalStateException if the tree is not empty
*/
public Node<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = new Node<E>(e, null, null);
return root;
}
/**
* Creates a new left child of Position p storing element e and returns its Position.
*/
public Node<E> addLeft(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getLeft() != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = new Node<E>(e, null, null);
p.setLeft(child);
return child;
}
/**
* Creates a new right child of Position p storing element e and returns its Position.
*/
public Node<E> addRight(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = new Node<E>(e,null, null);
p.setRight(child);
return child;
}
/**
* Replaces the element at Position p with element e and returns the replaced element.
*/
public E set(Node<E> p, E e) throws IllegalArgumentException {
E temp = p.getElement();
p.setElement(e);
return temp;
}
public void attach(Node<E> p, simpleLinkedBinaryTree<E> t1,
simpleLinkedBinaryTree<E> t2) throws IllegalArgumentException {
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
if (!t1.isEmpty()) { // attach t1 as left subtree of node
p.setLeft(t1.root);
t1.root = null;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
p.setRight(t2.root);
t2.root = null;
}
}
public E remove(Node<E> p) throws IllegalArgumentException {
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (p.getLeft() != null ? p.getLeft() : p.getRight() );
if (p == root)
root = child; // child becomes root
else {
Node<E> parent = (Node<E>) parent(p);
if (p == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
E temp = p.getElement();
p.setElement(null); // help garbage collection
p.setLeft(null);
p.setRight(null);
return temp;
}
//pre_order traversal
private void preorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
snapshot.add(p); // for preorder, we add position p before exploring subtrees
for (Node<E> c : children(p))
preorderSubtree(c, snapshot);
}
public ArrayList<Node<E>> preorder() {
ArrayList<Node<E>> snapshot = new ArrayList<>();
if (!isEmpty())
preorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//in_order traversal
private void inorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
if (left(p) != null)
inorderSubtree(left(p), snapshot);
snapshot.add(p);
if (right(p) != null)
inorderSubtree(right(p), snapshot);
}
public ArrayList<Node<E>> inorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
inorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//post_order traversal
private void postorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
for (Node<E> c : children(p))
postorderSubtree(c, snapshot);
snapshot.add(p); // for postorder, we add position p after exploring subtrees
}
public ArrayList<Node<E>> postorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
postorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
/****************************************************************************************/
/*****************Your LAB starts here!******************/
/****************************************************************************************/
//Returns the number of nodes in the tree.
public int size() {
}
//Returns the Node of p's parent (or null if p is root).
public Node<E> parent(Node<E> p1, Node<E> p2){
}
public boolean isIdentical(Node<E> p1, Node<E> p2){
}
public ArrayList<Node<E>> ancestors(Node<E> p1, Node<E> p2)
{
return null;
}
}
testClass.java:
package simpleBinaryTree;
import java.util.ArrayList;
public class testClass {
public static void main(String[] args)
{
simpleLinkedBinaryTree<Integer> myBtree = new simpleLinkedBinaryTree<Integer>();
myBtree.addRoot(5);
Node<Integer> left=myBtree.addLeft(myBtree.root(), 2);
myBtree.addLeft(left, 8);
myBtree.addRight(left, 10);
ArrayList<Node<Integer>> preorderList = myBtree.preorder();
for(Node<Integer> p: preorderList)
System.out.print(p.getElement()+" ");
System.out.println();
System.out.println("Number of Node on the tree: "+myBtree.size());
simpleLinkedBinaryTree<Integer> oBtree = myBtree;
System.out.println("Those two trees are identical: "+myBtree.isIdentical(myBtree.root, oBtree.root));
System.out.println("The parent node of "+ left.getElement() +" is" + myBtree.parent(myBtree.root, left));
ArrayList<Integer> ancestorlist = myBtree.ancestors(myBtree.root, left.getLeft());
for(Integer i: ancestorlist) System.out.print(i+" ");
}
}
Explanation / Answer
// Java program to connect nodes at same level using extended
// pre-order traversal
// A binary tree node
class Node
{
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root;
// Sets the nextRight of root and calls connectRecur()
// for other nodes
void connect(Node p)
{
// Set the nextRight for root
p.nextRight = null;
// Set the next right for rest of the nodes (other
// than root)
connectRecur(p);
}
/* Set next right of all descendents of p.
Assumption: p is a compete binary tree */
void connectRecur(Node p)
{
// Base case
if (p == null)
return;
// Set the nextRight pointer for p's left child
if (p.left != null)
p.left.nextRight = p.right;
// Set the nextRight pointer for p's right child
// p->nextRight will be NULL if p is the right most child
// at its level
if (p.right != null)
p.right.nextRight = (p.nextRight != null) ?
p.nextRight.left : null;
// Set nextRight for other nodes in pre order fashion
connectRecur(p.left);
connectRecur(p.right);
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* Constructed binary tree is
10
/
8 2
/
3
*/
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
// Populates nextRight pointer in all nodes
tree.connect(tree.root);
// Let us check the values of nextRight pointers
System.out.println("Following are populated nextRight pointers in "
+ "the tree" + "(-1 is printed if there is no nextRight)");
int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.data + " is "
+ a);
int b = tree.root.left.nextRight != null ?
tree.root.left.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.left.data + " is "
+ b);
int c = tree.root.right.nextRight != null ?
tree.root.right.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.right.data + " is "
+ c);
int d = tree.root.left.left.nextRight != null ?
tree.root.left.left.nextRight.data : -1;
System.out.println("nextRight of " + tree.root.left.left.data + " is "
+ d);
}
}
// Recursive Java program to connect nodes at same level
// using constant extra space
// A binary tree node
class Node
{
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root;
/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void connectRecur(Node p)
{
// Base case
if (p == null)
return;
/* Before setting nextRight of left and right children, set nextRight
of children of other nodes at same level (because we can access
children of other nodes using p's nextRight only) */
if (p.nextRight != null)
connectRecur(p.nextRight);
/* Set the nextRight pointer for p's left child */
if (p.left != null)
{
if (p.right != null)
{
p.left.nextRight = p.right;
p.right.nextRight = getNextRight(p);
}
else
p.left.nextRight = getNextRight(p);
/* Recursively call for next level nodes. Note that we call only
for left child. The call for left child will call for right child */
connectRecur(p.left);
}
/* If left child is NULL then first node of next level will either be
p->right or getNextRight(p) */
else if (p.right != null)
{
p.right.nextRight = getNextRight(p);
connectRecur(p.right);
}
else
connectRecur(getNextRight(p));
}
/* This function returns the leftmost child of nodes at the same
level as p. This function is used to getNExt right of p's right child
If right child of p is NULL then this can also be used for
the left child */
Node getNextRight(Node p)
{
Node temp = p.nextRight;
/* Traverse nodes at p's level and find and return
the first node's first child */
while (temp != null)
{
if (temp.left != null)
return temp.left;
if (temp.right != null)
return temp.right;
temp = temp.nextRight;
}
// If all the nodes at p's level are leaf nodes then return NULL
return null;
}
/* Driver program to test the above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.right.right = new Node(90);
// Populates nextRight pointer in all nodes
tree.connectRecur(tree.root);
// Let us check the values of nextRight pointers
int a = tree.root.nextRight != null ?
tree.root.nextRight.data : -1;
int b = tree.root.left.nextRight != null ?
tree.root.left.nextRight.data : -1;
int c = tree.root.right.nextRight != null ?
tree.root.right.nextRight.data : -1;
int d = tree.root.left.left.nextRight != null ?
tree.root.left.left.nextRight.data : -1;
int e = tree.root.right.right.nextRight != null ?
tree.root.right.right.nextRight.data : -1;
// Now lets print the values
System.out.println("Following are populated nextRight pointers in "
+ " the tree(-1 is printed if there is no nextRight)");
System.out.println("nextRight of " + tree.root.data + " is " + a);
System.out.println("nextRight of " + tree.root.left.data + " is " + b);
System.out.println("nextRight of " + tree.root.right.data + " is " + c);
System.out.println("nextRight of " + tree.root.left.left.data +
" is " + d);
System.out.println("nextRight of " + tree.root.right.right.data +
" is " + e);
}
}
//pre_order traversal
private void preorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
snapshot.add(p); // for preorder, we add position p before exploring subtrees
for (Node<E> c : children(p))
preorderSubtree(c, snapshot);
}
public ArrayList<Node<E>> preorder() {
ArrayList<Node<E>> snapshot = new ArrayList<>();
if (!isEmpty())
preorderSubtree(root(), snapshot); // fill the snapshot recursively
return snap;
}
//in_order traversal
private void inorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
if (left(p) != null)
inorderSubtree(left(p), snapshot);
snapshot.add(p);
if (right(p) != null)
inorderSubtree(right(p), snapshot);
}
public ArrayList<Node<E>> inorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
inorderSubtree(root(), snapshot); // fill the snapshot recursively
return snap;
}
//post_order traversal
private void postorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
for (Node<E> c : children(p))
postorderSubtree(c, snapshot);
snapshot.add(p); // for postorder, we add position p after exploring subtrees
}
public ArrayList<Node<E>> postorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
postorderSubtree(root(), snapshot); // fill the snap recursively
return snap;
}
// for finding that after swapping the nodes the answer will be the same
//ancestors of a given node
#include <bits/stdc++.h>
using namespace std;
// Data structure to store a Binary Tree node
struct Node
{
int data;
Node *left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
Node* node = new Node;
node->data = key;
node->left = node->right = nullptr;
return node;
}
// Function to insert given key into the tree
void insert(Node*& root, string level, int key)
{
// tree is empty
if (level.length() == 0)
{
root = newNode(key);
return;
}
int i = 0;
Node* ptr = root;
while (i < level.length() - 1)
{
if (level[i++] == 'L')
ptr = ptr->left;
else
ptr = ptr->right;
}
if (level[i] == 'L')
ptr->left = newNode(key);
else
ptr->right = newNode(key);
}
// Recursive function to print all ancestors of given node in a binary tree. The
// function returns true if node is found in subtree rooted at given root node
bool printAncestors(Node *root, int node)
{
// base case
if (root == nullptr)
return false;
// return true if given node is found
if (root->data == node)
return true;
// search node in left subtree
bool left = printAncestors(root->left, node);
// search node in right subtree
bool right = false;
if (!left)
right = printAncestors(root->right, node);
// if given node is found in either left or right subtree,
// current node is an ancestor of given node
if (left || right)
cout << root->data << " ";
// return true if node is found
return left || right;
}
// main function
int main()
{
Node* root = nullptr;
/* Construct below tree
1
/
/
2 3
/
4 5 6
/
7 8
*/
vector<pair<string, int>> keys =
{
{"", 1}, {"L", 2}, {"R", 3}, {"LR", 4},
{"RL", 5}, {"RR", 6}, {"RLL", 7}, {"RRR", 8}
};
for (auto pair: keys)
insert(root, pair.first, pair.second);
int node = 7;
printAncestors(root, node);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.