Header Ads Widget

Responsive Advertisement

How to get the neighbor of binary tree

Kartik Chandra Mandal January 08, 2018

To find the neighbors of a node in a binary tree recursively, you need to use a depth-first search (DFS) approach. The idea is to traverse the tree and keep track of the current level of nodes. When you find the target node, you can then collect all the nodes at the same level (excluding the target node) using a recursive helper function.

Problem Description

Given a binary tree and a target node, find the neighboring nodes of the target node. Neighbors of a node in a binary tree are considered to be the nodes that are at the same level (siblings).

Approach 1 using DFS:

  1. Recursive DFS Traversal: Traverse the tree recursively, keeping track of the level of each node.
  2. Identify Target Node: When you find the target node, note its level.
  3. Collect Neighbors: Use a recursive helper function to collect all nodes at the same level as the target node, excluding the target node itself.

Implementation in Java

Here is a detailed implementation of the described approach:

java

import java.util.*;

 

class TreeNode {

    int val;

    TreeNode left, right;

 

    TreeNode(int val) {

        this.val = val;

        left = right = null;

    }

}

 

public class BinaryTreeNeighbors {

 

    private int targetLevel;

    private boolean targetFound;

 

    public List<Integer> findNeighbors(TreeNode root, TreeNode target) {

        List<Integer> neighbors = new ArrayList<>();

        if (root == null || target == null) return neighbors;

 

        // Find the level of the target node

        targetLevel = -1;

        targetFound = false;

        findTargetLevel(root, target, 0);

 

        if (targetLevel == -1) return neighbors; // Target not found in the tree

 

        // Collect neighbors at the same level

        collectNeighbors(root, target, 0, neighbors);

        return neighbors;

    }

 

    private void findTargetLevel(TreeNode node, TreeNode target, int currentLevel) {

        if (node == null) return;

 

        if (node == target) {

            targetLevel = currentLevel;

            targetFound = true;

            return;

        }

 

        if (!targetFound) findTargetLevel(node.left, target, currentLevel + 1);

        if (!targetFound) findTargetLevel(node.right, target, currentLevel + 1);

    }

 

    private void collectNeighbors(TreeNode node, TreeNode target, int currentLevel, List<Integer> neighbors) {

        if (node == null) return;

 

        if (currentLevel == targetLevel && node != target) {

            neighbors.add(node.val);

        }

 

        collectNeighbors(node.left, target, currentLevel + 1, neighbors);

        collectNeighbors(node.right, target, currentLevel + 1, neighbors);

    }

 

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);

        root.right.right = new TreeNode(7);

 

        BinaryTreeNeighbors finder = new BinaryTreeNeighbors();

        TreeNode target = root.left; // Target node with value 2

        List<Integer> neighbors = finder.findNeighbors(root, target);

 

        System.out.println("Neighbors of node " + target.val + ": " + neighbors);

    }

}

 

Explanation

  1. TreeNode Class: Represents the structure of a binary tree node.
  2. findNeighbors Method:
    • Calls findTargetLevel to determine the level of the target node.
    • Calls collectNeighbors to collect all nodes at the same level as the target node.
  3. findTargetLevel Method:
    • Recursively traverses the tree to find the target node and sets the targetLevel.
  4. collectNeighbors Method:
    • Recursively traverses the tree and collects nodes that are at the same level as the target node (excluding the target node itself).
  5. Main Method:
    • Creates a sample binary tree.
    • Invokes the findNeighbors method to find and print the neighbors of a specified target node.

Running the Example

  • In the sample binary tree:

       1

     /   \

    2     3

   / \   / \

  4   5 6   7

 

    • If the target node is 2, the neighbors are 3 (since they are at the same level).
    • If the target node is 4, the neighbors are 5 (since they are at the same level).

 

Approach 2 using BFS:

  1. Level Order Traversal (BFS): Traverse the tree level by level using a queue.
  2. Identify Target Node Level: During traversal, keep track of the level of each node.
  3. Collect Neighbors: Once the target node is found, continue collecting nodes in the same level.

Implementation in Java

Here's the detailed implementation of the described approach:

java

import java.util.*;

 

class TreeNode {

    int val;

    TreeNode left, right;

   

    TreeNode(int val) {

        this.val = val;

        left = right = null;

    }

}

 

public class BinaryTreeNeighbors {

 

    // Method to find neighbors of a given target node

    public List<Integer> findNeighbors(TreeNode root, TreeNode target) {

        if (root == null || target == null) return new ArrayList<>();

 

        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

 

        while (!queue.isEmpty()) {

            int levelSize = queue.size();

            List<TreeNode> currentLevel = new ArrayList<>();

            boolean targetFound = false;

 

            for (int i = 0; i < levelSize; i++) {

                TreeNode currentNode = queue.poll();

                if (currentNode == target) {

                    targetFound = true;

                }

                currentLevel.add(currentNode);

                if (currentNode.left != null) queue.add(currentNode.left);

                if (currentNode.right != null) queue.add(currentNode.right);

            }

 

            if (targetFound) {

                List<Integer> neighbors = new ArrayList<>();

                for (TreeNode node : currentLevel) {

                    if (node != target) {

                        neighbors.add(node.val);

                    }

                }

                return neighbors;

            }

        }

 

        return new ArrayList<>(); // Target not found in the tree

    }

 

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);

        root.right.right = new TreeNode(7);

 

        BinaryTreeNeighbors finder = new BinaryTreeNeighbors();

        TreeNode target = root.left; // Target node with value 2

        List<Integer> neighbors = finder.findNeighbors(root, target);

       

        System.out.println("Neighbors of node " + target.val + ": " + neighbors);

    }

}

 

Explanation

  1. TreeNode Class: Represents the structure of a binary tree node.
  2. findNeighbors Method:
    • Uses a queue to perform a level order traversal (BFS).
    • For each level, it checks if the target node is present.
    • If the target node is found, it collects all nodes at that level (excluding the target node) as neighbors.
  3. Main Method:
    • Creates a sample binary tree.
    • Invokes the findNeighbors method to find and print the neighbors of a specified target node.

Running the Example

  • In the sample binary tree:

       1

     /   \

    2     3

   / \   / \

  4   5 6   7

 

    • If the target node is 2, the neighbors are 3 (since they are at the same level).
    • If the target node is 4, the neighbors are 5 (since they are at the same level).

 

This implementation demonstrates how to identify the neighbors of a given node in a binary tree using a recursive DFS approach. This method ensures that the neighbors (siblings) are correctly identified based on their level in the tree.

 

Problem Statement:

Find out the next neighbor of each node. If it is right node then print the null.  Purpose of this algorithm is found out the garbage collector of data node.

Approach 3 using Recursive:

1.       Recursive DFS Traversal: Traverse the tree recursively, keeping track of the level of each node.

2.       Identify Target Node: When you find the target node, note its level.

3.       Collect Neighbors: Use a recursive helper function to collect all nodes at the same level as the target node, excluding the target node itself.

Implementation in Java

Here is a detailed implementation of the described approach:

java

package com.kartik.neighbor.print;

 

public class Node

{

    int data;

    Node left, right, neighbor;

 

    Node(int data)

    {

        this.data = data;

        left = right = neighbor = null;

    }

}

 

 

package com.kartik.neighbor.print;

 

public class BinaryTree {

 int count = 5;

 

 Node root;

 

 // Sets the nextRight of root and calls connectRecur()

 // for other nodes

 void connect(Node node) {

 

  // Set the nextRight for root

  node.neighbor = null;

 

  // Set the next right for rest of the nodes (other

  // than root)

  getNeighbor(node);

 }

 

 /*

  * Set next right of all descendents of p. Assumption: node is a compete

  * binary tree

  */

 void getNeighbor(Node node) {

 

  /*

   * Constructed binary tree is

      1

      /     \

     2       3

    /  \    / \

   4    5  6   7

   */

  // Base case

  if (node == null)

   return;

  // Set the nextRight pointer for p's left child

  if (node.left != null)

   node.left.neighbor = node.right;

 

  // Set the nextRight pointer for p's right child

  // p.nextRight will be NULL if p is the right most child

  // at its level

  if (node.right != null)

   node.right.neighbor = (node.neighbor != null) ? node.neighbor.left

     : null;

 

  String a = node.neighbor != null ? String.valueOf(node.neighbor.data)

    : null;

  System.out.println("nextRight of -->>>" + node.data + " is " + a);

 

  // Set nextRight for other nodes in pre order fashion

  getNeighbor(node.left);

  getNeighbor(node.right);

 }

 

 // Function to print binary tree in 2D

 // It does reverse inorder traversal

 void print2DUtil(Node root, int space) {

  // Base case

  if (root == null)

   return;

  // Increase distance between levels

  space += count;

  // Process right child first

  print2DUtil(root.right, space);

  // Print current node after space

  // count

  System.out.println("\n");

  for (int i = count; i < space; i++)

   System.out.print(" ");

  System.out.println(root.data);

  // Process left child

  print2DUtil(root.left, space);

 }

 

 // Wrapper over print2DUtil()

 void print2D(Node root) {

  // Pass initial space count as 0

  print2DUtil(root, 0);

 }

 

 // Driver program to test above functions

 public static void main(String args[]) {

  BinaryTree tree = new BinaryTree();

        

        /* Constructed binary tree is

                15

 

 

          7

 

 

               14

 

 

     3

 

 

               13

 

 

          6

 

 

               12

 

 

1

 

 

               11

 

 

          5

 

 

     2

 

 

               9

 

 

          4

 

 

               8

        */

  tree.root = new Node(1);

  tree.root.left = new Node(2);

  tree.root.right = new Node(3);

  // tree.root.left.left = new Node(3);

 

  tree.root.left.left = new Node(4);

  tree.root.left.right = new Node(5);

  tree.root.right.left = new Node(6);

  tree.root.right.right = new Node(7);

 

  tree.root.left.left.left = new Node(8);

  tree.root.left.left.right = new Node(9);

  // tree.root.left.right.left = new Node(10);

  tree.root.left.right.right = new Node(11);

  tree.root.right.left.left = new Node(12);

  tree.root.right.left.right = new Node(13);

  tree.root.right.right.left = new Node(14);

  tree.root.right.right.right = new Node(15);

  // Populates nextRight pointer in all nodes

  tree.print2D(tree.root);

  tree.connect(tree.root);

    }

}

 

 

 

Explanation

1.       Node Class: Represents the structure of a binary tree node.

2.       Connect Method:

a.       Calls getNeighbor to determine the level of the target node.

3.       getNeighbor Method:

a.       Recursively traverses the tree to find the target node and sets the targetLevel.

4.       print2DUtil Method:

a.       Recursively traverses the tree and collects nodes that are at the same level as the target node with space .

5.       Main Method:

a.       Creates a sample binary tree.

b.       Invokes the Connect method to find and print the neighbors of a specified target node.

Running the Example

  • In the sample binary tree:

         15

 

 

          7

 

 

               14

 

 

     3

 

 

               13

 

 

          6

 

 

               12

 

 

1

 

 

               11

 

 

          5

 

 

     2

 

 

               9

 

 

          4

 

 

               8

nextRight of -->>>1 is null

nextRight of -->>>2 is 3

nextRight of -->>>4 is 5

nextRight of -->>>8 is 9

nextRight of -->>>9 is null

nextRight of -->>>5 is 6

nextRight of -->>>11 is 12

nextRight of -->>>3 is null

nextRight of -->>>6 is 7

nextRight of -->>>12 is 13

nextRight of -->>>13 is 14

nextRight of -->>>7 is null

nextRight of -->>>14 is 15

nextRight of -->>>15 is null

 


neighbor of binary tree
neighbor of binary tree 





Post a Comment

0 Comments

Post a Comment