Dado un árbol binario de Nodes distintos y un par de Nodes. La tarea es encontrar e imprimir la ruta entre los dos Nodes dados en el árbol binario.
Por ejemplo , en el árbol binario anterior, la ruta entre los Nodes 7 y 4 es 7 -> 3 -> 1 -> 4 .
La idea es encontrar rutas desde los Nodes raíz a los dos Nodes y almacenarlos en dos vectores o arrays separados, digamos ruta1 y ruta2.
Ahora bien, se plantean dos casos diferentes:
- Si los dos Nodes están en diferentes subárboles de Nodes raíz . Ese es uno en el subárbol izquierdo y el otro en el subárbol derecho. En este caso, está claro que el Node raíz estará entre la ruta del Node 1 al Node 2. Entonces, imprima la ruta 1 en orden inverso y luego la ruta 2.
- Si los Nodes están en el mismo subárbol . Eso está en el subárbol izquierdo o en el subárbol derecho. En este caso, debe observar que la ruta desde la raíz hasta los dos Nodes tendrá un punto de intersección antes del cual la ruta es común para los dos Nodes desde el Node raíz. Encuentre ese punto de intersección e imprima los Nodes desde ese punto de manera similar al caso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print path between any
// two nodes in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// structure of a node of binary tree
struct Node {
int data;
Node *left, *right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* getNode(int data)
{
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to check if there is a path from root
// to the given node. It also populates
// 'arr' with the given path
bool getPath(Node* root, vector<int>& arr, int x)
{
// if root is NULL
// there is no path
if (!root)
return false;
// push the node's value in 'arr'
arr.push_back(root->data);
// if it is the required node
// return true
if (root->data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (getPath(root->left, arr, x) || getPath(root->right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// Thus, remove current node's value from
// 'arr'and then return false
arr.pop_back();
return false;
}
// Function to print the path between
// any two nodes in a binary tree
void printPathBetweenNodes(Node* root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
vector<int> path1;
// vector to store the path of
// second node n2 from root
vector<int> path2;
getPath(root, path1, n1);
getPath(root, path2, n2);
int intersection = -1;
// Get intersection point
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
// Keep moving forward until no intersection
// is found
if (i == j && path1[i] == path2[j]) {
i++;
j++;
}
else {
intersection = j - 1;
break;
}
}
// Print the required path
for (int i = path1.size() - 1; i > intersection; i--)
cout << path1[i] << " ";
for (int i = intersection; i < path2.size(); i++)
cout << path2[i] << " ";
}
// Driver program
int main()
{
// binary tree formation
struct Node* root = getNode(0);
root->left = getNode(1);
root->left->left = getNode(3);
root->left->left->left = getNode(7);
root->left->right = getNode(4);
root->left->right->left = getNode(8);
root->left->right->right = getNode(9);
root->right = getNode(2);
root->right->left = getNode(5);
root->right->right = getNode(6);
int node1 = 7;
int node2 = 4;
printPathBetweenNodes(root, node1, node2);
return 0;
}
Java
// Java program to print path between any
// two nodes in a Binary Tree
import java.util.*;
class Solution
{
// structure of a node of binary tree
static class Node {
int data;
Node left, right;
}
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node getNode(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// Function to check if there is a path from root
// to the given node. It also populates
// 'arr' with the given path
static boolean getPath(Node root, Vector<Integer> arr, int x)
{
// if root is null
// there is no path
if (root==null)
return false;
// push the node's value in 'arr'
arr.add(root.data);
// if it is the required node
// return true
if (root.data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (getPath(root.left, arr, x) || getPath(root.right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// Thus, remove current node's value from
// 'arr'and then return false
arr.remove(arr.size()-1);
return false;
}
// Function to print the path between
// any two nodes in a binary tree
static void printPathBetweenNodes(Node root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
Vector<Integer> path1= new Vector<Integer>();
// vector to store the path of
// second node n2 from root
Vector<Integer> path2=new Vector<Integer>();
getPath(root, path1, n1);
getPath(root, path2, n2);
int intersection = -1;
// Get intersection point
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
// Keep moving forward until no intersection
// is found
if (i == j && path1.get(i) == path2.get(i)) {
i++;
j++;
}
else {
intersection = j - 1;
break;
}
}
// Print the required path
for ( i = path1.size() - 1; i > intersection; i--)
System.out.print( path1.get(i) + " ");
for ( i = intersection; i < path2.size(); i++)
System.out.print( path2.get(i) + " ");
}
// Driver program
public static void main(String[] args)
{
// binary tree formation
Node root = getNode(0);
root.left = getNode(1);
root.left.left = getNode(3);
root.left.left.left = getNode(7);
root.left.right = getNode(4);
root.left.right.left = getNode(8);
root.left.right.right = getNode(9);
root.right = getNode(2);
root.right.left = getNode(5);
root.right.right = getNode(6);
int node1 = 7;
int node2 = 4;
printPathBetweenNodes(root, node1, node2);
}
}
// This code is contributed by Arnab Kundu
Python
# Python3 program to print path between any
# two nodes in a Binary Tree
import sys
import math
# structure of a node of binary tree
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
# Helper function that allocates a new node with the
#given data and NULL left and right pointers.
def getNode(data):
return Node(data)
# Function to check if there is a path from root
# to the given node. It also populates
# 'arr' with the given path
def getPath(root, rarr, x):
# if root is NULL
# there is no path
if not root:
return False
# push the node's value in 'arr'
rarr.append(root.data)
# if it is the required node
# return true
if root.data == x:
return True
# else check whether the required node lies
# in the left subtree or right subtree of
# the current node
if getPath(root.left, rarr, x) or getPath(root.right, rarr, x):
return True
# required node does not lie either in the
# left or right subtree of the current node
# Thus, remove current node's value from
# 'arr'and then return false
rarr.pop()
return False
# Function to print the path between
# any two nodes in a binary tree
def printPathBetweenNodes(root, n1, n2):
# vector to store the path of
# first node n1 from root
path1 = []
# vector to store the path of
# second node n2 from root
path2 = []
getPath(root, path1, n1)
getPath(root, path2, n2)
# Get intersection point
i, j = 0, 0
intersection=-1
while(i != len(path1) or j != len(path2)):
# Keep moving forward until no intersection
# is found
if (i == j and path1[i] == path2[j]):
i += 1
j += 1
else:
intersection = j - 1
break
# Print the required path
for i in range(len(path1) - 1, intersection - 1, -1):
print("{} ".format(path1[i]), end = "")
for j in range(intersection + 1, len(path2)):
print("{} ".format(path2[j]), end = "")
# Driver program
if __name__=='__main__':
# binary tree formation
root = getNode(0)
root.left = getNode(1)
root.left.left = getNode(3)
root.left.left.left = getNode(7)
root.left.right = getNode(4)
root.left.right.left = getNode(8)
root.left.right.right = getNode(9)
root.right = getNode(2)
root.right.left = getNode(5)
root.right.right = getNode(6)
node1=7
node2=4
printPathBetweenNodes(root,node1,node2)
# This Code is Contributed By Vikash Kumar 37
C#
// C# program to print path between any
// two nodes in a Binary Tree
using System;
using System.Collections.Generic;
class Solution
{
// structure of a node of binary tree
public class Node
{
public int data;
public Node left, right;
}
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node getNode(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// Function to check if there is a path from root
// to the given node. It also populates
// 'arr' with the given path
static Boolean getPath(Node root, List<int> arr, int x)
{
// if root is null
// there is no path
if (root == null)
return false;
// push the node's value in 'arr'
arr.Add(root.data);
// if it is the required node
// return true
if (root.data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (getPath(root.left, arr, x) || getPath(root.right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// Thus, remove current node's value from
// 'arr'and then return false
arr.RemoveAt(arr.Count-1);
return false;
}
// Function to print the path between
// any two nodes in a binary tree
static void printPathBetweenNodes(Node root, int n1, int n2)
{
// vector to store the path of
// first node n1 from root
List<int> path1 = new List<int>();
// vector to store the path of
// second node n2 from root
List<int> path2 = new List<int>();
getPath(root, path1, n1);
getPath(root, path2, n2);
int intersection = -1;
// Get intersection point
int i = 0, j = 0;
while (i != path1.Count || j != path2.Count)
{
// Keep moving forward until no intersection
// is found
if (i == j && path1[i] == path2[i])
{
i++;
j++;
}
else
{
intersection = j - 1;
break;
}
}
// Print the required path
for ( i = path1.Count - 1; i > intersection; i--)
Console.Write( path1[i] + " ");
for ( i = intersection; i < path2.Count; i++)
Console.Write( path2[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
// binary tree formation
Node root = getNode(0);
root.left = getNode(1);
root.left.left = getNode(3);
root.left.left.left = getNode(7);
root.left.right = getNode(4);
root.left.right.left = getNode(8);
root.left.right.right = getNode(9);
root.right = getNode(2);
root.right.left = getNode(5);
root.right.right = getNode(6);
int node1 = 7;
int node2 = 4;
printPathBetweenNodes(root, node1, node2);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to print path between any
// two nodes in a Binary Tree
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
function getNode(data)
{
let newNode = new Node(data);
return newNode;
}
// Function to check if there is a path from root
// to the given node. It also populates
// 'arr' with the given path
function getPath(root, arr, x)
{
// if root is null
// there is no path
if (root==null)
return false;
// push the node's value in 'arr'
arr.push(root.data);
// if it is the required node
// return true
if (root.data == x)
return true;
// else check whether the required node lies
// in the left subtree or right subtree of
// the current node
if (getPath(root.left, arr, x) || getPath(root.right, arr, x))
return true;
// required node does not lie either in the
// left or right subtree of the current node
// Thus, remove current node's value from
// 'arr'and then return false
arr.pop();
return false;
}
// Function to print the path between
// any two nodes in a binary tree
function printPathBetweenNodes(root, n1, n2)
{
// vector to store the path of
// first node n1 from root
let path1= [];
// vector to store the path of
// second node n2 from root
let path2 = [];
getPath(root, path1, n1);
getPath(root, path2, n2);
let intersection = -1;
// Get intersection point
let i = 0, j = 0;
while (i != path1.length || j != path2.length) {
// Keep moving forward until no intersection
// is found
if (i == j && path1[i] == path2[i]) {
i++;
j++;
}
else {
intersection = j - 1;
break;
}
}
// Print the required path
for ( i = path1.length - 1; i > intersection; i--)
document.write( path1[i] + " ");
for ( i = intersection; i < path2.length; i++)
document.write( path2[i] + " ");
}
// binary tree formation
let root = getNode(0);
root.left = getNode(1);
root.left.left = getNode(3);
root.left.left.left = getNode(7);
root.left.right = getNode(4);
root.left.right.left = getNode(8);
root.left.right.right = getNode(9);
root.right = getNode(2);
root.right.left = getNode(5);
root.right.right = getNode(6);
let node1 = 7;
let node2 = 4;
printPathBetweenNodes(root, node1, node2);
</script>
Producción:
7 3 1 4
Complejidad de tiempo: O(N), ya que estamos usando la recursividad para atravesar el árbol. Donde N es el número de Nodes en el árbol.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra para almacenar los caminos de los árboles. Donde N es el número de Nodes en el árbol.