Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is data structure?
4.2.
What is a nonlinear data?
4.3.
What is binary tree used for?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print all nodes that are at distance k from a leaf node

Author Harsh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Data structure and algorithms are one of the most important topics to understand if you want to work for a top product-based company. To have a complete understanding of DSA, you must solve a variety of code challenges. In this blog, we'll look at a coding problem in which we need to print the nodes that are exactly K distance away from the leaf node in our binary tree.

Problem Statement

Ninja has given you an integer K and a binary tree. Your task is to print all the nodes present in the binary tree that are exactly K distance away from a leaf node. In this case, k distance away from a leaf denotes k levels higher than a leaf node.

Sample Examples

Input

Output

Explanation

Node 4 and node 5 are exactly 2 distances away from leaf nodes 1, 8 and 3.

 

Example 2

Input

Output

Explanation

Only node 5 is 3 distance away from the leaf node.

Approach

Create two arrays one will store the path to the node and the other one will be used to keep track of the visited nodes. If the current node is null then get the node at distance K from the current node using the path array and print it on the screen otherwise call the function recursively with child nodes.

Algorithm

ALGORITHM(node, path[], visited[], len, k)
    if node is null:
        return;
    
    path[len] <- node->data
    visited[len] <- false
    len <- len + 1

    if node->left is NULL and node->right is NULL and len - k - 1 >= 0 and visited[len - k - 1] is false:
        print (path[len - k - 1])
        visited[len - k - 1] <- true
        return

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// our node
class Node
{
public:
    int data;
    Node *left;
    Node *right;

    Node(int data)
    {
        this->data = data;
        left = nullptr;
        right = nullptr;
    }
};

/*
    function to print all nodes that are exactly K distance away from leaf node.
    here variable Path is used to store the ancestors of a node and
    the visited array keeps track of visited nodes.
    len is used to keep track of distance from a node
*/
void k_distance_from_leaf(Node *node, vector<int> &path, vector<bool> &visited,
                          int len, int k)
{
    // return null if root node is null
    if (node == nullptr)
        return;

    /* appending current Node to the path */
    path[len] = node->data;
    visited[len] = false;
    len++;

    // if current node is leaf node then print its ancestors that are K distance away
    if (node->left == nullptr && node->right == nullptr && len - k - 1 >= 0 && visited[len - k - 1] == false)
    {
        cout << path[len - k - 1] << " ";
        visited[len - k - 1] = true;
        return;
    }

    // if current node is not a leaf node then
    // call the function with its child nodes
    k_distance_from_leaf(node->left, path, visited, len, k);
    k_distance_from_leaf(node->right, path, visited, len, k);
}

// main function
int main()
{
    int k = 2;
    Node *root = new Node(5);
    root->left = new Node(4);
    root->right = new Node(3);
    root->left->left = new Node(9);
    root->left->right = new Node(8);
    root->left->left->right = new Node(1);

    cout << "Nodes at distance " << k << " from leaf node: ";

    // maximum height of tree
    int max_height = 10000;
    vector<int> path(max_height);
    vector<bool> visited(max_height, false);

    k_distance_from_leaf(root, path, visited, 0, k);

    cout << endl;

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

Nodes at distance 2 from leaf node: 4 5 

Time Complexity

The time complexity of the above program is O(n) as we are only doing a simple tree traversal.

Space Complexity

We are using visited and path arrays to store the details. So, the space complexity of the above program is O(max_height), where max_height is the maximum height of the tree defined in the program.

Optimized Approach

In the above approach, we are using two arrays to store the details. We can use another space-optimized approach to solve this problem. We are using two variables to keep track of the leaf node if the value of both of the variables is 0 then it means that the current node is a leaf node at that time we’ll return the k-1 value from our function and at any point if the value of k reaches 0 that means that our current node is exactly k distance away from the leaf node.

Algorithm

ALGORITHM(node, k)
    if node is NULL:
        return
    
    left <- ALGORITHM(node->left, k)
    right <- ALGORITHM(node->right, k)

    if left == right and left = -1 and node is LeafNode:
        print(node)
    
    if node is LeafNode and K > 0:
        return k - 1

    if left > 0 and left < k:
        return left - 1

    if right > 0 and right < k:
        return right - 1

    return -2

Implementation in C++

#include <bits/stdc++.h>
using namespace std;


// our node
class Node {
public:
int data;
Node* left;
Node* right;


    Node(int data){
        this->data = data;
        left = nullptr;
        right = nullptr;
    }
};


// function to print nodes that are k distance away from leaf node
int k_distance_from_leaf(Node *node, int k) {


    // if current node is null return -1
    if (node == nullptr) return -1;


    // storing the value returned by our function
    int left = k_distance_from_leaf(node->left, k);
    int right = k_distance_from_leaf(node->right, k);


    // boolean to check if the current node is a leaf node or not
    bool isLeaf = left == -1 && left == right;


    // if current node is the leaf node and K is 0
    // then print the value of current node
    if (left == 0 || right == 0 || (isLeaf && k == 0))
        cout<<(" " )<<( node->data);


    // if current node is a leaf node and k is greater than 0 then return k - 1
    if (isLeaf && k > 0)
        return k - 1;


    // parent of left leaf node
    if (left > 0 && left < k)
        return left - 1; 


    // parent of right leaf node
    if (right > 0 && right < k)
        return right - 1; // parent of right leaf


    return -2;
}


// main function
int main() {
    int k = 2;
    Node* root = new Node(5);
    root->left = new Node(4);
    root->right = new Node(3);
    root->left->left = new Node(9);
    root->left->right = new Node(8);
    root->left->left->right = new Node(1);


    cout << "Nodes at distance " << k << " from leaf node: ";


    k_distance_from_leaf(root, k);


    cout << endl;


return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

Nodes at distance 2 from leaf node:  4 5

Time Complexity

The time complexity of the above program is O(n) as we are only doing a simple tree traversal.

Space Complexity

We are not using any extra space. So, the Space complexity of our program is O(1).

Frequently Asked Questions

What is data structure?

A data structure is a specific format for storing, organising, and processing data. There are a variety of simple and advanced data structures available, all of which are designed to organise data for a specific purpose.
 

What is a nonlinear data?

A non-linear data structure has no fixed sequence for connecting all of its elements, and each member can connect to other elements by various paths. Such data structures allow for multi-level storage and are frequently inaccessible in a single run.
 

What is binary tree used for?

Binary trees are mostly utilized in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most popular operations on binary trees.

Conclusion

In this article, we have extensively discussed a coding problem where we have to print the all nodes of a binary tree that are K distance away from leaf node.

We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more, check out our articles Level Order Traversal Of  A Binary TreePrint the node values at odd levels of a Binary treeReplace each node in a binary tree with the sum of its inorder predecessor and successor, and many more on our Website.

Check out this problem - Root To Leaf Path
 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Learning!

 

Live masterclass