patterncsharpMinor
Find lowest leaf nodes in a binary tree
Viewed 0 times
nodeslowestleafbinaryfindtree
Problem
So this is probably a popular problem, and I decided to take a crack at it today using C#.
I came up with the following solution:
This is a recursive function using a
Could this solution be written more efficiently?
Also, would it be easier to parallelize using a functional language like Clojure, or is that not really a factor as long as variables are not passed by reference?
I came up with the following solution:
private BinaryTree.BinaryTreeNode FindLowestNodes(BinaryTree.BinaryTreeNode node, int depth, ref int biggestDepth) {
this.WriteResult("Entering recursiorn for node.....{0}", node.Value.ToString());
BinaryTree.BinaryTreeNode lowestNode = null;
if (node.Left != null) {
var n = FindLowestNodes(node. Left, depth + 1, ref biggestDepth);
if (n != null) lowestNode = n;
}
if (node.Right != null) {
var n = FindLowestNodes(node.Right, depth + 1, ref biggestDepth);
if (n != null)
lowestNode = n;
}
if (node.Left == null && node.Right == null) {
if (depth > biggestDepth) {
lowestNode = node;
biggestDepth = depth;
}
}
return lowestNode;
}This is a recursive function using a
depth parameter, and biggestDepth parameter that helps me determine if the node is indeed the lowest since the tree can have multiple depths. What I don't like about passing an int by reference is boxing...Could this solution be written more efficiently?
Also, would it be easier to parallelize using a functional language like Clojure, or is that not really a factor as long as variables are not passed by reference?
Solution
Passing an int with the
Your code seems quite efficient to me, I have nothing to comment on.
ref keyword does not involve any boxing at all. Do not confuse this with "passing an int by reference" (as in, a function with return type Object returning an int,) which is quite a different thing, and it does involve boxing. Your code seems quite efficient to me, I have nothing to comment on.
Context
StackExchange Code Review Q#7564, answer score: 2
Revisions (0)
No revisions yet.