Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored the approach of Boundary Traversal of Binary Tree along with Time and Space Complexity.

**Contents**:

## Introduction

When we capture only elements that exist on the **Boundary** of the Binary Tree is the kind of traversing, is what "Boundary Traversal of Binary Tree" refers to.

For example:

**We can collect three following types of nodes**:

**1. (1&2) left end nodes and right end nodes**

These are the nodes that you can see on every level, and on every level they exists on the very beginning of the level or on the very end of the level, if we take above diagram as an example, then,

**Left end nodes:** `[5, 4, -3, -2, -4, 12]`

**Right end nodes:** `[5, 6, 10, -1, 11]`

**3. leaf nodes**

Any node that has no child will be considered as a leaf nodes. So, again if we take above diagram as reference, then,

**Leaf nodes:** `[12, 7, 9, 11]`

Traversing of Binary Tree can be done in two manners,

`clock-wise`

**and**

`anti-clockwise`

.

For `clockwise`

first, we collect all the `right end`

nodes and then the `leaf`

nodes while reading it from right-to-left and then all the `left end`

nodes from the bottom `leaf`

node to the `root`

of the tree.

And in case of `anti-clockwise`

Of course, we will implement `clockwise`

traversing in exact reverse.

Or we could just reverse the result of `clockwise`

traversing to get the result for `anti-clockwise`

.

Note:In the result, we cannot have duplicate nodes, but we may have duplicate values.

For example, we cannot read the root node in both`right end`

traverse and`left end`

traverse. i.e. we would have to remove`5`

from them, depending if we do`clockwise`

or`anti-clockwise`

.

## Implementation

#### Node:

Of course, first we need a tree before we could traverse it. For that we can create a class `Node`

, which will have three attributes for a

`value`

: which can store a value or a pointer to something, we will be storing unique values, so, we can represent both ideas at the same time.`pointer to the left child`

**And**`pointer to the right child`

.

Something like,

```
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_leaf(self):
return self.left is None and self.right is None
```

defining an extra method called `is_leaf`

, just to make our code more readable.

##### Methods

Let's define some methods, to divide the work of traversing between them.

###### Reading `left end`

nodes:

To read all left end nodes on each level. We can write a recursive method or a loop that will it's child, but we will priortize `left`

child over `right`

child and store them in a list or array or recommended would be linked list.

This way, we can visit `left`

most child on every level and if in case, left child is `None`

( not available ) then we will visit the `right`

child, because, in this case `right`

child should act as the *left most* or to say *left end* child.

And one more requirement is to exclude both `root`

and the last `left end`

node, hence, `root`

and left most `leaf`

node. Why? because as we noted this above that we cannot have redundancy.

```
def all_lefts(self):
lefts = []
node = self
while True:
if node.left is not None:
node = node.left
elif node.right is not None:
node = node.right
else:
return lefts[:-1]
lefts.append(node.val)
```

Here, `return lefts[:-1]`

will exclude the leaf node that would be include in the 2^{nd} last iteration.

And, to exclude the `root`

node, we are starting the checks on the child nodes, which will automatically do that.

if you want to `break`

in 2^{nd} last iteration itself, you can replace `else:`

with:

```
if node.is_leaf():
return lefts
```

###### Reading `right end`

nodes:

To read `right end`

nodes, we will follow the exact same idea as above the only thing we need to change here is the priority for the `right child`

node over the `left child`

node and everything should work as expected.

```
def all_rights(self):
rights = []
node = self
while True:
if node.right is not None:
node = node.right
elif node.left is not None:
node = node.left
else:
return rights[:-1]
rights.append(node.val)
```

Note:that we're visiting the only one child node and not the other, for which we're using`if elif`

, but while reading leafs we will be using two seperate`if`

statements.

##### reading leafs

When we want the result for `anti-clockwise`

then the leafs should be read from `left-to-right`

and for `clockwise`

leafs should be read from `right-to-left`

.

To capture leafs we can create a recursive function, in which we can prioritize visiting `left`

child first for `left-to-right`

result and can prioritize visiting `right`

child first for `right-to-left`

result.

###### reading leafs from left-to-right:

```
def leafs_lr(self, leafs=[]):
if self.is_leaf():
leafs.append(self.val)
if self.left is not None:
leafs = self.left.leafs_lr(leafs)
if self.right is not None:
leafs = self.right.leafs_lr(leafs)
return leafs
```

###### reading leafs from right-to-left:

```
def leafs_rl(self, leafs=[]):
if self.is_leaf():
leafs.append(self.val)
if self.right is not None:
leafs = self.right.leafs_rl(leafs)
if self.left is not None:
leafs = self.left.leafs_rl(leafs)
return leafs
```

###### Traversing Clockwise:

Now if we use above defined methods to Traverse Clockwise, then sequence to use them would be:

`[self.val]`

=> This will give us the root node, since, that's where we will be starting from.`self.all_rights()`

=> To get the nodes from`root`

node till`right end`

node.`self.leafs_rl()`

=> This will return from`right end`

to`left end`

node.`self.all_lefts()[::-1]`

=> And here we're reversing the`all_lefts`

, therefore, we will get the list of nodes from`left end`

nodes to`root`

.

And then we will add the above statements all together.

```
def traverse_clockwise(self):
return [self.val] + self.all_rights() + self.leafs_rl() + self.all_lefts()[::-1]
```

###### Traversing Anti-Clockwise:

We will follow the same Idea as above, but only in opposite direction, from which we get the following code:

```
def traverse_anti_clockwise(self):
return [self.val] + self.all_lefts() + self.leafs_lr() + self.all_rights()[::-1]
```

Well, Of course, one can do `self.traverse_clockwise()[::-1]`

and will get the same result for `self.traverse_anti_clockwise()`

.

##### Result

Let's take the diagram we saw above as an example.

```
tree = Node(5)
# lefts
tree.left = Node(4)
tree.left.left = Node(-3)
tree.left.right = Node(1)
tree.left.right.left = Node(7)
tree.left.right.right = Node(9)
tree.left.left.left = Node(2)
tree.left.left.left.right = Node(-4)
tree.left.left.left.right.right = Node(12)
# rights
tree.right = Node(6)
tree.right.right = Node(10)
tree.right.right.right = Node(-1)
tree.right.right.right.left = Node(11)
```

Sorry! for the above verbosity.

And now if we use `traverse_clockwise()`

and `traverse_anti_clockwise()`

on `tree`

we should get:

```
print(tree.traverse_clockwise())
print(tree.traverse_anti_clockwise())
```

Output:

```
[5, 6, 10, -1, 11, 9, 7, 12, -4, 2, -3, 4]
[5, 4, -3, 2, -4, 12, 7, 9, 11, -1, 10, 6]
```

## Complexity

###### Time Complexity

Since, Binary Tree has some numbers of nodes, then let's its `N`

number of nodes.

Now, the operations we performed on the *Tree* to get the answer, were,

- lefts
- rights
- leafs

For lefts and rights, in every iteration, we go down a level in the tree, and there are $\log_2{N}$ number of levels in a Binary Tree.

For leafs, we recursively visit every node in the Binary Tree, and there are $N$ numbers of nodes.

According to above points the Time complexity should be $O(2\log_2{N} + N)$,

i.e.

$$O(N)$$

There could be a case when Binary Tree will consist of only two leaf nodes, for example, if we remove `Node(1)`

, `Node(7)`

and `Node(9)`

from the above example, then it should create such Binary Tree,

and in this kind of Binary Tree, the Time Complexity will become $O(\log_2{N})$

###### Space Complexity

As for space complexity, when we traverse the Binary Tree we do create a `list`

of nodes found for three different operations

And, there can only exist $\log_2{N}$ numbers of lefts and rights, but for reading leafs, there can exist `[1, N/2]`

of leaf nodes, therefore total space complexity for Boundary Traversing results to

$$O(N)$$

And again if we find only `2`

leafs in a Binary Tree then the space complexity can also result in $O(\log_2{N})$.

And In the case of the Binary Tree which is only the root node, will have both Time and Space Complexity of $O(1)$.

With this article at OpenGenus, you must have the complete idea of Boundary Traversal of Binary Tree.