What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Find Distance between Two Nodes of a Binary Tree (with code)

  • Jul 19, 2023
  • 7 Minutes Read
  • Why Trust Us
    We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
  • By Harshita Rajput
Find Distance between Two Nodes of a Binary Tree (with code)

In computer science and data structures, a binary tree is a fundamental data structure that consists of nodes connected by edges. One common task when working with binary trees is determining how far are two nodes from each other. In this article, we will explore different approaches to calculating the distance between two nodes in a binary tree.

Distance between Two Nodes in Binary Tree

First, let's revise some basics of a binary tree. It is a hierarchical structure that consists of nodes connected by edges. Each node in a binary tree contains a value and can have at most two children: a left child and a right child.

The left child represents a node that is less than or equal to the current node's value, while the right child represents a node that is greater than the current node's value. The children of a node can themselves be binary trees, forming sub-trees of the overall structure.

binary tree example

In the above image, there is a binary tree with a root node as A.

So, let's now understand our problem. Here is the problem statement: "Given a root of a binary tree and two nodes. We need to find the distance between these 2 nodes. The distance here is the minimum number of edges to be traversed to reach from one node to another."

Let's understand the problem with an example:

distance between two nodes example

Here we need to find the distance between Node 7 and Node 8. Both nodes are 3 edges away from each other, so the answer is 3.

Algorithm to Find Distance between Two Nodes

Here is the step-by-step algorithm to find the distance between two nodes in a binary tree:

  1. First, we will find the node-to-root path for both nodes in the form of two ArrayLists.
  2. Then we begin from the last indices of both the ArrayLists.
  3. If the value at both indices is the same, we decrease the pointers.
  4. If both indices have different indices, we break and increase the pointer count by 1.
  5. The pointers are pointing to the node where the path diverged for both the given nodes.
  6. In the end, we return the answer by adding the length of ArrayList - pointer of both array lists.

Code for Implementation

Following is the simple programming code to find the distance between two nodes in a binary tree:

public static int distanceBetweenNodes(Node node, int d1, int d2) {
    // finding node to root path for both the nodes
    ArrayList< Integer> path1 = nodeToRootPath(node, d1);
    ArrayList< Integer> path2 = nodeToRootPath(node, d2);
    // setting the pointer to the last index of arraylists
    int pointer1 = path1.size() - 1;
    int pointer2 = path2.size() - 1;
    // finding the diverging node 
    while (pointer1 >= 0 && pointer2 >= 0 && path1.get(pointer1) == path2.get(pointer2)) {
    //returning the edges
    return pointer1 + pointer2;
  public static ArrayList< Integer> nodeToRootPath(Node node, int data) {
    if (node.data == data) {
      ArrayList< Integer> path = new ArrayList< >();
      return path;

    for (Node child : node.children) {
      ArrayList< Integer> list = nodeToRootPath(child, data);
      if (list.size() > 0) {
        return list;

    return new ArrayList< >();


Time & Space Complexity

The time complexity of the given code is O(N), where N is the number of nodes in the binary tree. This is because in the worst case, we may need to traverse the entire tree to find the node-to-root paths for both nodes.

The space complexity of the code is O(N), where N is the number of nodes in the binary tree. This is because we are using ArrayLists to store the node-to-root paths, and in the worst case, the paths can contain all the nodes in the tree. Therefore, the space required is proportional to the number of nodes in the tree.


This task is commonly used in many scenarios in the programming world. Here are some common applications:

  • Network Routing: The distance between nodes in a binary tree can be utilized in network routing algorithms. For example, in a hierarchical routing scheme, where nodes are organized in a binary tree structure, the distance between nodes can help determine the shortest path or the most efficient route for transmitting data between two specific nodes.
  • Tree Traversals: The distance between two nodes can be used to define the relative position of nodes during tree traversals. For example, in an in-order traversal, the distance between two nodes can help identify the order in which they appear in the traversal.
  • Binary Tree Diameter: The distance between the two farthest nodes is known as the diameter of the binary tree. By finding the distance between every pair of nodes in the tree, we can determine the maximum distance and hence the diameter of the tree.


By understanding these approaches, you can efficiently determine the distance between two nodes in a binary tree and solve related problems in various applications.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Harshita Rajput
I am a highly motivated individual with a deep passion for technology and programming. My exceptional performance in programming contests, and my dedication to solving data structures and algorithmic problems on global platforms, demonstrate my commitment to the field of technology.