Reaching all the nodes at specific height

[lost110]

I have been trying to make logic for this but it's not working. The user will give a value for height. At that specific height I have to check which node has the least children. I have to print that node. It is for an AVL TREE. When the tree becomes big, things get confusing.How would the pointer move to all the required positions?

[jonnin]

you need to do a traversal and you stop, not as normal when the pointer you want to follow is null, but under more complex conditions … where the pointer is null OR the depth is whatever. You have to keep track of the depth in the recursion, which you can do with either a static variable in the recursive routine or passing it along in the params. IF you reach the required depth, THEN you need to check the pointers for null to count up the children. You also need to STORE the best candidate solution as you find them. I suppose you can quit if you find one with no children -- your requirement is odd and not 100% clear on whether that is OK to do?

alternate lazy solution: you can store 'my depth' and 'my # of children' (must keep children up to date on insert/delete / etc) as part of your data for each tree node and then just traverse it and look at those. (you can still short circuit if your depth gets > value desired). Depending on how you did delete, depth may need updates too. I dunno if this is much simpler or just spreading the pieces around.

[lost110]

So now I just want to print all the nodes at specific height (level) . And tell that how much childrens they have. The code is running but giving printing wrong data! If I input data in this way : 10,6,15,7,8,16 ! It would be a balance tree : https://ibb.co/3pcsD3L
And according to my function "printkdistance" the nodes at height 2 should be 5, 7 and 16! But it is telling information regarding 5(at height 2) , 8(at height 3) and 15 (at height 1).

#include<iostream>
using namespace std;
struct AVL {
	int height;
	int data;
	AVL *left;
	AVL *right;
};
AVL *root = NULL;
int max(int num1, int num2) {
	return (num1 > num2) ? num1 : num2;
}
int height(AVL *root) {
	if (root == NULL)
	{
		return 0;
	}
	root->height = max(height(root->left), height(root->right)) + 1;
	return root->height;
}
int balance(AVL *root) {
	if (root == NULL) {
		return 0;
	}
	return (height(root->left) - height(root->right));
}
AVL *rotate_right(AVL *root) {
	AVL *newroot = root->left;
	root->left = newroot->right;
	newroot->right = root;
	newroot->height = max(height(newroot->left), height(newroot->right)) + 1;
	root->height = max(height(root->left), height(root->right)) + 1;
	return newroot;
}
AVL *rotate_left(AVL *root) {
	AVL *newroot = root->right;
	root->right = newroot->left;
	newroot->left = root;
	newroot->height = max(height(newroot->left), height(newroot->right)) + 1;
	root->height = max(height(root->left), height(root->right)) + 1;
	return newroot;
}
AVL *insert(AVL *root, AVL *node) {
	if (root == NULL) {
		root = node;
	}
	else if (node->data < root->data) {
		root->left = insert(root->left, node);
	}
	else if (node->data > root->data) {
		root->right = insert(root->right, node);
	}
	else {
		return root;
	}
	int b = balance(root);
	root->height = 1 + max(height(node->left), height(node->right));
	if (b > 1 && node->data < root->left->data) {
		return rotate_right(root);
	}
	else if (b > 1 && node->data > root->left->data) {
		root->left = rotate_left(root->left);
		return rotate_right(root);
	}
	else if (b < -1 && node->data > root->right->data) {
		return rotate_left(root);
	}
	else if (b < -1 && node->data < root->right->data) {
		root->right = rotate_left(root->right);
		return rotate_left(root);
	}
	return root;
}
void show(AVL *root) {
	if (root == NULL) {
		return;
	}
	else {
		show(root->left);
		cout << "Height " << root->height;
		cout << "\tData " << root->data << endl;
		show(root->right);
	}
}
void printKDistant(AVL *root, int k)
{
	if (root == NULL)
		return;
	if (k == 0)
	{
		if (root->left == NULL && root->right == NULL)
		{
			cout << "NODE WITH DATA" << root->data << " has least children ";
		}
		else if (root->left == NULL || root->right == NULL)
		{
			cout << "NODE WITH DATA  " << root->data << " has one children" << endl;
		}
		if (root->left != NULL && root->right != NULL)
		{
			cout << "NODE WITH DATA  " << root->data << " has max children" << endl;
		}
		return;
	}
	else
	{
		printKDistant(root->left, k - 1);
		printKDistant(root->right, k - 1);
	}
}
int main()
{
	int num,height;
	cout << "How Many Nodes You Want to Create: ";
	cin >> num;
	for (int i = 0; i < num; i++) 
	{
		AVL *node = new AVL;
		cout << "Enter Data:- ";
		cin >> node->data;
		node->left = NULL;
		node->right = NULL;
		node->height = 1;
		root = insert(root, node);
	}
	cout << "Enter height at which you want to check the childrens of respected nodes" << endl;
	cin >> height;
	printKDistant(root, height);
	system("pause");
}

[dhayden]

I'd approach this like peeling an onion. Figure out what you need from all angles (top down and bottom up):

The top level routing is something like:

// Return a pointer to the node is tree root that is (1) at the specified depth and (2)
// has the fewest children
Node *leastChildrenAtDepth(Node *root, unsigned depth);

And you need a function to count children:
unsigned numChildren(Node *);

And you need an internal version of leastChildrenAtDepth that will return both the node and the number of children:

// Like above, but it sets count to the number of children in the returned node.
Node *leastChildrenAtDepth(Node* node, unsigned depth, unsigned &count);

General hint for recursion: I always code recursive functions with this pattern:

if (base case) {
    // return base value;
} else {
    // Do the recursive case
}

This forces your to think of the two cases separately. It also ensures that you don't forget about the base case,which is a very common mistake.