Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
can we include the case for node with 1 node by modifying the recursion condition this way:
if(node.left)
printBorder(node.left, leftMost, false);
else if(node.right)
printBorder(node.right, leftMost, false);
if(node.right)
printBorder(node.right, false, rightMost);
else if(node.left)
printBorder(node.left, false, rightMost);
We break the problem in 3 parts:
1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
…..2.1 Print all leaf nodes of left sub-tree from left to right.
…..2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.
We need to take care of one thing that nodes are not printed again. e.g. The left most node is also the leaf node of the tree.
Based on the above cases, below is the implementation:
/* program for boundary traversal of a binary tree */
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node *left, *right;
};
// A simple function to print leaf nodes of a binary tree
void printLeaves(struct node* root)
{
if ( root )
{
printLeaves(root->left);
// Print it if it is a leaf node
if ( !(root->left) && !(root->right) )
printf("%d ", root->data);
printLeaves(root->right);
}
}
// A function to print all left boundry nodes, except a leaf node.
// Print the nodes in TOP DOWN manner
void printBoundaryLeft(struct node* root)
{
if (root)
{
if (root->left)
{
// to ensure top down order, print the node
// before calling itself for left subtree
printf("%d ", root->data);
printBoundaryLeft(root->left);
}
else if( root->right )
{
printf("%d ", root->data);
printBoundaryLeft(root->right);
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}
}
// A function to print all right boundry nodes, except a leaf node
// Print the nodes in BOTTOM UP manner
void printBoundaryRight(struct node* root)
{
if (root)
{
if ( root->right )
{
// to ensure bottom up order, first call for right
// subtree, then print this node
printBoundaryRight(root->right);
printf("%d ", root->data);
}
else if ( root->left )
{
printBoundaryRight(root->left);
printf("%d ", root->data);
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}
}
// A function to do boundary traversal of a given binary tree
void printBoundary (struct node* root)
{
if (root)
{
printf("%d ",root->data);
// Print the left boundary in top-down manner.
printBoundaryLeft(root->left);
// Print all leaf nodes
printLeaves(root->left);
printLeaves(root->right);
// Print the right boundary in bottom-up manner
printBoundaryRight(root->right);
}
}
// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);
printBoundary( root );
return 0;
}
Output:
20 8 4 10 14 25 22
Simple Recursive solution:
public void printBorder(TreeNode root)
{
System.out.print(root.element+ " ");
printLeftBorderExceptLastElement(root.left);
printAllLeafNodes(root);
printRightBorderReverseExceptLastElement(root.right);
}
private void printRightBorderReverseExceptLastElement(TreeNode root) {
if(root.right==null)
{
if(root.left!=null)
{
printRightBorderReverseExceptLastElement(root.left);
System.out.print(root.element +" ");
}
return;
}
printRightBorderReverseExceptLastElement(root.right);
System.out.print(root.element + " ");
}
private void printAllLeafNodes(TreeNode root) {
if(root==null)
return;
if(root.left==null && root.right==null)
{
System.out.print(root.element + " ");
return;
}
printAllLeafNodes(root.left);
printAllLeafNodes(root.right);
}
private void printLeftBorderExceptLastElement(TreeNode root) {
if(root.left==null )
{
if(root.right!=null)
{
System.out.print(root.element + " ");
printLeftBorderExceptLastElement(root.right);
}
return;
}
System.out.print(root.element+ " ");
printLeftBorderExceptLastElement(root.left);
}
Time Complexity is O(n)
Space Complexity is O(h)=>O(n)
Please correct me if I'm wrong.
If a left side node X has only right node and also X is not a leaf, how would you take careof it? Same way at right side too.
(1) Perform BFS (breadth-first search) on the tree
(2) For each level in the BFS, include the first & last nodes at each level. Include the last only if it's different from the first.
(3) Include all the nodes at the bottom-most level
(4) Return the list of nodes you have included from (2) & (3)
static List<Node> border(Node node) {
ArrayList<LinkedList<Node>> bfs = new ArrayList<LinkedList<Node>>();
LinkedList<Node> currentLevel = new LinkedList<Node>();
currentLevel.add(node);
do {
bfs.add(currentLevel);
LinkedList<Node> nextLevel = new LinkedList<Node>();
for(Node n : currentLevel) {
if(n.left != null)
nextLevel.add(n.left);
if(n.right != null)
nextLevel.add(n.right);
}
currentLevel = nextLevel;
} while(!currentLevel.isEmpty());
LinkedList<Node> borderNodes = new LinkedList<Node>();
for(int i=0; i<bfs.size()-1; i++) {
currentLevel = bfs.get(i);
borderNodes.add(currentLevel.getFirst());
if(currentLevel.getLast() != currentLevel.getFirst())
borderNodes.add(currentLevel.getLast());
}
borderNodes.addAll(bfs.get(bfs.size()-1));
return borderNodes;
}
public void printBorder(TreeNode<Integer> root, TreeNode<Integer> current) {
if (current == null) {
return;
}
printBorder(root, current.getLeftChild());
if (current.getLeftChild() == null && current.getRightChild() == null)
System.out.println(current.getData());
else if (root.getData() > current.getData()) {
TreeNode<Integer> right = current.getRightChild();
if (right != null && current.getLeftChild() == null) {
System.out.println(current.getData());
}
} else if (root.getData() < current.getData()) {
TreeNode<Integer> left = current.getLeftChild();
if (left != null && current.getRightChild() == null) {
System.out.println(current.getData());
}
}
printBorder(root, current.getRightChild());
}
public void printBorder(TreeNode<Integer> root) {
printBorder(root, root);
}
Print left and right separately. The ones that doesn;'t have any children also contributo to boundary.
public static void main(String[] args) {
printingBoundary = "left";
System.out.println(root.data);
print(root.left, "left");
printingBoundary = "right";
print(root.right, "right");
}
static void print(BinaryTreeNode root, String boundary) {
if (root.left != null)
print(root.left, "left");
if (root.left == null && root.right == null)
System.out.println(root.data);
else if(boundary.equals(printingBoundary))
System.out.println(root.data);
if (root.right != null)
print(root.right, "right");
}
1.traverse all the left nodes of the tree
2.traverse all the right nodes of the tree
3.print the base nodes of the tree
//code
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node *right;
struct node *left;
}*root=NULL;
struct node *bst_ins(struct node *root,int n)
{
struct node *temp=root,*temp1;
if(!root)
{
root=new node;
root->data=n;
root->right=NULL;
root->left=NULL;
}
else
{
temp=root;
while(temp)
{
temp1=temp;
if(n>temp->data)
temp=temp->right;
else
temp=temp->left;
}
temp=new node;
temp->data=n;
temp->right=NULL;
temp->left=NULL;
if(n>temp1->data)
temp1->right=temp;
else
temp1->left=temp;
}
return root;
}
int display_boundaryl(struct node *root)
{
struct node *temp=root;
while(temp&&temp->left)
{
printf("%d ",temp->data);
temp=temp->left;
}
return 0;
}
int display_boundaryb(struct node *root)
{
struct node *temp=root;
if(!temp)return 0;
if(!temp->left&&!temp->right)printf("%d ",temp->data);
display_boundaryb(temp->left);
display_boundaryb(temp->right);
}
int display_boundaryr(struct node *root,struct node *temp)
{
if(root->right)
display_boundaryr(root->right,temp);
if(root!=temp&&(!(!root->left&&!root->right)))
printf("%d ",root->data);
return 0;
}
int del_tree(struct node *root)
{
if(root)
{
del_tree(root->right);
del_tree(root->left);
}
delete root;
return 0;
}
int main()
{
int i,n,d;
printf("enter the number of elements to be inserted into the tree:\n");
scanf("%d",&n);
printf("enter the elements of the tree:\n");
for(i=0;i<n;i++)
{
scanf("%d",&d);
root=bst_ins(root,d);
}
display_boundaryl(root);
display_boundaryb(root);
display_boundaryr(root,root);
del_tree(root);
return 0;
}
public void printBorder() {
printBorder(root);
}
private void printBorder(Node node) {
if (node == null) return;
System.out.println(node.data);
Node nleft = node.left, nright = node.right;
while(nleft.left != null) {
if(nleft == null) break;
if(nleft.left != null) System.out.println(nleft.data);
nleft = nleft.left;
}
printLeafNodes(node);
while(nright.right != null) {
if(nright == null) break;
if(nright.right != null) System.out.println(nright.data);
nright = nright.right;
}
}
private void printLeafNodes(Node node) {
if (node == null) return;
printLeafNodes(node.left);
if (node.left == null && node.right == null)
System.out.println(node.data);
printLeafNodes(node.right);
}
Assuming binary tree means every node has either two or no children (pass true for leftMost & rightMost initially):
static void printBorder(Node node, boolean leftMost, boolean rightMost) { if(node == null) return; if(leftMost || rightMost || (node.left == null && node.right == null)) System.out.println(node.value); printBorder(node.left, leftMost, false); printBorder(node.right, false, rightMost); }If we can't make that assumption then see my other solution using BFS.
- Sunny April 21, 2013