Coderust: Hacking the Coding Interview/

...

/

Print Tree Perimeter

Print Tree Perimeter

Given a binary tree, print its perimeter nodes.

We'll cover the following...

Statement

Given the root node of a binary tree, print the nodes that form its perimeter (boundary). We must print the perimeter of the binary tree in three phases (order is important):

  1. Left boundary
  2. Leaf nodes
  3. Right boundary

Example

In the following tree, the nodes highlighted in green, form the perimeter.

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 60 node1->node4 node6 350 node2->node6 node7 10 node3->node7 node8 70 node4->node8 node9 400 node6->node9

The expected output for the tree above is: 100, 50, 25, 10, 70, 400, 350, 200.

Sample input

The input list below represents the level-order traversal of the binary tree:

[100, 50, 200, 25, 60, 350, 10, 70, 400]

Expected output

The sequence below represents the perimeter of the binary tree:

100, 50, 25, 10, 70, 400, 350, 200

Try it yourself

Note: The binary tree node’s class has members left and right to store references to other nodes, along with the member data to hold the node’s value.

main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include "BinaryTree.cpp"
#include <stack>
#include <string>
using namespace std;
void DisplayTreePerimeter(BinaryTreeNode* root) {
	// TODO: Write - Your - Code
	cout << "";
}

Solution 1

We print the perimeter of the binary tree in three phases, the left boundary, leaf nodes, and the right boundary. The left and right boundaries will be printed iteratively while the leaf nodes will be printed recursively. Here is how the algorithm looks:

  • Print the root node.
  • Print the left boundary in top-down order.
  • Print the leaf nodes in left-right order. We’ll be traversing from one leaf node to the next using post-order traversal.
  • Print the right boundary in bottom-up order.
    • We push the node values in a stack here.
    • Once we hit the leaf node, we pop all stack elements while printing them.
main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include "BinaryTree.cpp"
#include <string>
#include <stack>
using namespace std;
// Function to print left tree perimeter
void PrintLeftPerimeter(BinaryTreeNode* root, string& result) {
	while (root != nullptr) {
		int curr_val = root->data;
		// Setting root such that left boundary nodes are printed from top to bottom
		if (root->left != nullptr) {
			root = root->left;
		} else if (root->right != nullptr) {
			root = root->right;
		} else {
			// Break loop on leaf node
			break;
		}
		// Append current node to perimeter result
		result += to_string(curr_val) + ", ";
	}
}
// Function to print right tree perimeter
void PrintRightPerimeter(BinaryTreeNode* root, string& result) {
	// Stack for right side values.
	stack<int> r_values;
	while (root != nullptr) {
		int curr_val = root->data;
		// Setting root such that right boundary nodes are stored in stack of
		// right-side values from top to bottom
		if (root->right != nullptr) {
			root = root->right;
		} else if (root->left != nullptr) {
			root = root->left;
		} else {
			// Break loop on leaf node
			break;
		}
		r_values.push(curr_val);
	}
	// Appending nodes in reverse order to perimeter result
	while (r_values.empty() == false) {
		result += to_string(r_values.top()) + ", ";
		r_values.pop();
	}
}
// Function to print leaf nodes perimeter
void PrintLeafNodes(BinaryTreeNode* root, string& result) {
	// Recursively traversing to leaf nodes
	if (root != nullptr) {
		PrintLeafNodes(root->left, result);
		PrintLeafNodes(root->right, result);
		// Append node to result if it's a leaf node
		if (root->left == nullptr && root->right == nullptr) {
			result += to_string(root->data) + ", ";
		}
	}
}
void DisplayTreePerimeter(BinaryTreeNode* root) {
	string result = "";
	if (root != nullptr) {
		// If the tree is not null , we immediately add root to our perimeter result
		result += to_string(root->data) + ", ";
		// Calling function to print left boundary node
		PrintLeftPerimeter(root->left, result);
		// Calling function to print leaf nodes
		if (root->left != nullptr || root->right != nullptr) {
			// We don't need to print if root is also the leaf node.
			PrintLeafNodes(root, result);
		}
		// Calling function to print right boundary node
		PrintRightPerimeter(root->right, result);
		// Removing trailing comma and space from our result
		if (result.length() > 2) {
			result = result.substr(0, result.length() - 2);
		}
		cout << result;
	}
}
int main() {
	// Creating a binary tree
	vector<int> input1 = {100, 50, 200, 25, 75, 125, 350, 250, 750, 12, 35, 60, 80, 110, 150};
	BinaryTree *tree1 = new BinaryTree(input1);
	// Creating a binary tree with wrong node in left subtree
	BinaryTree *tree2 = new BinaryTree(100);
	tree2->Insert(50);
	tree2->Insert(200);
	tree2->Insert(25);
	// Add a node at an incorrect position
	tree2->InsertBT(110);
	tree2->Insert(125);
	tree2->Insert(350);
	tree2->Insert(250);
	tree2->Insert(750);
	tree2->Insert(12);
	tree2->Insert(35);
	tree2->InsertBT(60);
	tree2->InsertBT(80);
	tree2->InsertBT(120);
	// Creating a binary tree with wrong node in right subtree
	BinaryTree *tree3 = new BinaryTree(100);
	tree3->Insert(50);
	tree3->Insert(200);
	tree3->Insert(25);
	tree3->Insert(75);
	// Add a node at an incorrect position
	tree3->InsertBT(90);
	tree3->Insert(350);
	tree3->Insert(250);
	tree3->Insert(750);
	tree3->Insert(12);
	tree3->Insert(35);
	tree3->InsertBT(60);
	tree3->InsertBT(80);
	tree3->InsertBT(110);
	// Creating a right degenerate binary tree
	vector<int> input4 = {25, 50, 75, 100, 125, 200, 350};
	BinaryTree *tree4 = new BinaryTree(input4);
	// Creating a left degenerate binary tree
	vector<int> input5 = {350, 200, 125, 100, 75, 50, 25};
	BinaryTree *tree5 = new BinaryTree(input5);
	// Creating a single node binary tree
	BinaryTree *tree6 = new BinaryTree(100);
	// Defining Test Cases
	vector<BinaryTreeNode*> test_cases_roots = {tree1->root, tree2->root, tree3->root, tree4->root, tree5->root, tree6->root, nullptr};
	for (int i = 0; i < test_cases_roots.size(); i++) {
		if (i > 0) {
			cout << endl;
		}
		cout << i + 1 << ".\tBinary tree" << endl;
		DisplayTree(test_cases_roots[i]);
		cout << "\n\tTree Perimeter:\n\t";
		DisplayTreePerimeter(test_cases_roots[i]);
		cout << "\n----------------------------------------------------------------------------------------------------\n";
	}
}

Time complexity

The Time complexity of ...