In this post, we are going to solve the 545. Boundary of Binary Tree problem of Leetcode. This problem 545. Boundary of Binary Tree is a Leetcode medium level problem. This is a part of Leetcode Premium Problem.
Let’s see the code, 545. Boundary of Binary Tree – Leetcode Solution.
Problem
Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.
Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary.
Note this definition only applies to the input binary tree, and not applies to any subtrees.
The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.
The right-most node is also defined by the same way with left and right exchanged.
Example 1 :
Input:
1
\
2
/ \
3 4
Ouput:
[1, 3, 4, 2]
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].Example 2 :
Input:
____1_____
/ \
2 3
/ \ /
4 5 6
/ \ / \
7 8 9 10
Ouput:
[1,2,4,7,8,9,10,6,3]
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].Constraints
- The number of nodes in the tree is in the range
[0, 104]. -100 <= Node.val <= 100
Now, let’s see the code of 545. Boundary of Binary Tree – Leetcode Solution.
Boundary of Binary Tree – Leetcode Solution
545. Boundary of Binary Tree – Solution in Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isLeaf(Node root){
return (root.left == null) && (root.right == null);
}
public void addLeftBoundary(Node node, ArrayList<Node> left){
if(node == null) return;
if(isLeaf(node) == false) left.add(node);
if(node.left != null) addLeftBoundary(node.left,left);
else addLeftBoundary(node.right,left);
}
public void addRightBoundary(Node node, ArrayList<Node> right){
if(node == null) return;
if(isLeaf(node) == false) right.add(node);
if(node.right != null) addRightBoundary(node.right,right);
else addRightBoundary(node.left,right);
}
public void addLeaf(Node node, ArrayList<Node> leaf){
if(node == null) return;
if(isLeaf(node) == true){
leaf.add(node);
return;
}
if(node.left != null) addLeaf(node.left,leaf);
if(node.right != null) addLeaf(node.right,leaf);
}
public List<Integer> boundaryOfBinaryTree(Node node)
{
List<Integer> ans = new ArrayList<Integer>();
ArrayList<Node> leftSide = new ArrayList<Node>();
ArrayList<Node> rightSide = new ArrayList<Node>();
ArrayList<Node> leaf = new ArrayList<Node>();
ans.add(node.data);
if(isLeaf(node) == true) return ans;
addLeftBoundary(node.left,leftSide);
addLeaf(node,leaf);
addRightBoundary(node.right,rightSide);
for(Node e : leftSide){
ans.add(e.data);
}
for(Node e : leaf){
ans.add(e.data);
}
for(int i = rightSide.size() - 1; i>=0 ; i--){
ans.add(rightSide.get(i).data);
}
return ans;
}
}
545. Boundary of Binary Tree – Solution in C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
bool isLeaf(TreeNode* root) {
return !root->left && !root->right;
}
void addLeaves(TreeNode* root, vector<int>& res) {
if (isLeaf(root)) {
res.push_back(root->val);
return;
}
if (root->left) addLeaves(root->left, res);
if (root->right) addLeaves(root->right, res);
}
public:
vector<int> boundaryOfBinaryTree(TreeNode* root) {
if (!root) return {};
vector<int> res;
if (!isLeaf(root)) res.push_back(root->val);
// add left boundary
TreeNode* cur = root->left;
while (cur) {
if (!isLeaf(cur)) res.push_back(cur->val);
if (cur->left) cur = cur->left;
else cur = cur->right;
}
// add leaf nodes
addLeaves(root, res);
cur = root->right;
vector<int> tmp;
// add right boundary
while (cur) {
if (!isLeaf(cur)) tmp.push_back(cur->val);
if (cur->right) cur = cur->right;
else cur = cur->left;
}
for (int i = tmp.size()-1; i >= 0; --i) {
res.push_back(tmp[i]);
}
return res;
}
};
545. Boundary of Binary Tree – Solution in Python
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
if root is None: return []
res=[root.val]
def leftBoundary(root):
if root is None or root.left is None and root.right is None: return
res.append(root.val)
if root.left:
leftBoundary(root.left)
else:
leftBoundary(root.right)
def rightBoundary(root):
if root is None or root.left is None and root.right is None: return
if root.right:
rightBoundary(root.right)
else:
rightBoundary(root.left)
res.append(root.val)
def leaves(node):
if node is None: return
if node.left is None and node.right is None and node != root:
res.append(node.val)
leaves(node.left)
leaves(node.right)
leftBoundary(root.left)
leaves(root)
rightBoundary(root.right)
return res
Note: This problem 545. Boundary of Binary Tree which is a leetcode premium problem and is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.