Leetcode.com problem 783: "Minimum Distance Between BST Nodes"

James S. Plank

Fri Apr 21 15:08:46 EDT 2023

Problem Statement.
Category: Easy
Success Rate (as of April, 2023): 59.3%
Skeleton.cpp: A skeleton file with a main.

Problem description in case Leetcode's servers are down

(I don't have testing for this program, so you'll have to use Leetcode to test.)

You have the following definition of a TreeNode, which stores a node in a binary tree:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

In case those last three lines look a little confusing to you, those are three constructors: You can construct a tree node with a value of 0 and no children, a tree node with a given value and no children, or a tree node with a given value and given children.

Your job is to write the method minDiffInBST in the class Solution, with the following prototype:

class Solution {
  public:
    int minDiffInBST(TreeNode* root);
};

Here's a description of the tree and what minDiffInBST() should return:

root is the root of a binary search tree.
Each node in the tree has a val between 0 and 100,000.
The tree has between 2 and 100 nodes.
You are to return the minimum difference between any two nodes in the tree.

Here are three examples in ASCII art:

Answer: 1

Answer: 1

Answer: 4

Driver program and testing

(This is the same driver program as http://web.eecs.utk.edu/~jplank/topcoder-writeups/Leetcode/Sum-Root-To-Leaf-Numbers/index.html, which I went over in COSC202).

The driver program in Skeleton.cpp reads a Tree on standard input by reading numbers:

First the value of the root
Then the values of the two children of the root (the two nodes at level 1)
Then the values of the four children of those children (the four nodes at level 2)
And so on. You don't need to complete the last level.

If there is no node, then a value of -1 should be specified. So, here are the three examples above:

UNIX> cat example-1.txt
4
2 6
1 3
UNIX> cat example-2.txt
1
0 48
-1 -1 12 49  # We need two -1's to take the place of the two children of node 3.
UNIX> cat example-3.txt
20 10 30 1 16  # Formatting doesn't matter
UNIX>

Hints

You can solve this with a postorder traversal, where, for each node of the tree, you store three values:

rv: The minimum difference between any two nodes in the subtree rooted by the node.
min: The minimum value in the subtree rooted by the node.
max: The max value in the subtree rooted by the node.

Here are the nodes with that information in example 3:

      20
      rv:4
      min:1
      max:30
     /      \
    /        \
   10         30
   rv:6       rv:-
   min:1      min:30
   max:16     max:30
  /      \
 /        \
1          16
rv:-       rv:-
min:1      min:16
max:1      max:16

I'm going to leave it up to you to figure out how you do this calculation with a postorder traversal, and I'm also going to leave it up to you how to write the program. What I did was define the following method in the Solution class:

void postorder(TreeNode *root, int &rv, int &min, int &max);

Please feel free to use that method definition to structure your answer.