Search⌘ K
Home
Courses
Decode the Coding Interview in Ruby: Real-World Examples

Boundary of Binary Tree

Explore how to identify and return the boundary of a binary tree by understanding its components: root, left boundary, leaves, and right boundary. Learn recursive techniques to traverse each boundary and apply them in coding interviews.

We'll cover the following...

Description

Let’s start by defining what a boundary of a binary tree is. We can define it as:

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary. Take a look at the example given below:

Take a look at the example given below:

As mentioned above, the boundary can be divided into four categories; the following explains these categories:

  • Root node

  • Left boundary

    • The root node’s left child is in the left boundary. If the root does not have a left child, the left boundary is empty.
    • If a node in the left boundary has a left child, the left child is in the left boundary.
    • If a node in the left boundary has a right child but no left child, the right child is in the left boundary.
    • The leftmost leaf is not in the left boundary.

  • Right boundary

    • The right boundary is similar to the left boundary, except it is on the right side of the root's right subtree.
    • The leaf is not part of the right boundary.
    • The right boundary is empty if the root does not have a right child.

  • Leaves

    • The leaves are nodes that do not have any children. For this problem, we can assume that the root is not a leaf.

Considering the definition of the boundary ...