If I had a binary search tree like the one in the image what would a traversal method look like, that could recursively find the path that weighs the most?
I tried doing an inOrder traversal but don't think I was writing it correctly. So an example that could work for this would be much appreciated.
edit:
private static void inOrder(BinaryNode tree) {
if(tree == null) return;
if (tree is an end node) {
update the end node array
}
if(tree.rightchild != null) {
parent[rightChild.getLabel()] = tree;
}
if(tree.leftChild != null) {
parent[leftChild.getLabel()] = tree;
}
inOrder(tree.leftChild);
inOrder(tree.rightChild);
}
Class that supports the one I'm trying to write
// Basic BinaryNode class, Feel free to edit this case.
public class BinaryNode {
private String label; // The label of the node
private BinaryNode[] childs; // childs[0] points to the left child, and childs[1] points to the right child
private int[] weights; // weights[0] is the funness of the left ski path from here, and weights[1]
// is the funness of the right ski path from here.
private boolean edge;
// Feel free to add extra data fields and methods to cater to your implementation.
// However, please do not edit anything that is already provided, as these are needed
// to build the tree from the input.
// Constructor
public BinaryNode(String label, BinaryNode left, BinaryNode right, int lw, int rw) {
this.label = label;
this.childs = new BinaryNode[]{left, right};
this.weights = new int[]{lw, rw};
}
// Accessors and Mutators
public BinaryNode getLeftChild() {
return childs[0];
}
public void setLeftChild(BinaryNode child) {
this.childs[0] = child;
}
public BinaryNode getRightChild() {
return childs[1];
}
public void setRightChild(BinaryNode child) {
this.childs[1] = child;
}
public int getLeftWeight() {
return weights[0];
}
public void setLeftWeight(int child) {
this.weights[0] = child;
}
public int getRightWeight() {
return weights[1];
}
public void setRightWeight(int child) {
this.weights[1] = child;
}
public String getLabel() {
return this.label;
}
public String toString() {
return "Node: " this.label;
}
}
// Don't Edit this class
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class BinaryTree {
private BinaryNode root;
private HashMap<String, BinaryNode> nodes;
private ArrayList<String[]> fileLinesToProcess;
public BinaryTree(){
this.nodes = new HashMap<>();
Scanner kb = new Scanner(System.in);
this.fileLinesToProcess = customRead(kb);
if(this.fileLinesToProcess.size() != 0){
int i = 0;
String[] shouldBeRoot = this.fileLinesToProcess.get(0);
this.root = new BinaryNode(shouldBeRoot[0], null, null, 0, 0);
this.nodes.put(shouldBeRoot[0], this.root);
while(this.fileLinesToProcess.size() != i){
String[] line = this.fileLinesToProcess.get(i);
BinaryNode tnode = this.nodes.getOrDefault(line[0], null);
BinaryNode othernode = this.nodes.getOrDefault(line[1], null);
if(tnode == null){
tnode = new BinaryNode(line[0], null, null, 0, 0);
}
if(othernode == null){
othernode = new BinaryNode(line[1], null, null, 0, 0);
}
this.nodes.put(line[0], tnode);
this.nodes.put(line[1], othernode);
if(tnode.getLeftChild() == null){
tnode.setLeftChild(othernode);
tnode.setLeftWeight(Integer.parseInt(line[2]));
}else{
tnode.setRightChild(othernode);
tnode.setRightWeight(Integer.parseInt(line[2]));
}
i ;
}
}
}
private ArrayList<String[]> customRead(Scanner fileInp){
ArrayList<String[]> output = new ArrayList<>();
while(fileInp.hasNext()){
String[] nums = fileInp.nextLine().split(" ");
output.add(nums);
}
return output;
}
public BinaryNode getRoot(){
return this.root;
}
public static void turnBSTtoString(BinaryNode root){
if(root == null) return;
if(root.getLeftChild() != null){
System.out.println(root.getLabel() " " root.getLeftChild().getLabel() " " root.getLeftWeight());
}
if(root.getRightChild() != null){
System.out.println(root.getLabel() " " root.getRightChild().getLabel() " " root.getRightWeight());
}
turnBSTtoString(root.getLeftChild());
turnBSTtoString(root.getRightChild());
return;
}
}
sample input: sample output: output for the tree image shown
CodePudding user response：
You could create a recursive function, like that inorder function, but the inorder code you presented is wrong in many respects as it doesn't even use existing properties of the BinaryNode class.
That recursive function should return the maximum weight and corresponding path it finds in the tree rooted at the given node. The base case occurs when the given node is null. In that case that maximum weight is 0, and the path is empty.
There are several ways you can think of organising the return value. I went for an ArrayList<Integer> whose first entry is the maximum weight, and all other entries are either 0 or 1 to represent a walk to the left or to the right.
Here is that function:
private static ArrayList<Integer> heaviestPath(BinaryNode root) {
if (root == null) return new ArrayList<Integer>() {{ add(0); }};
ArrayList<Integer> leftPath = heaviestPath(root.getLeftChild());
ArrayList<Integer> rightPath = heaviestPath(root.getRightChild());
if (leftPath.get(0) < rightPath.get(0)) {
rightPath.set(0, rightPath.get(0) root.getRightWeight());
rightPath.add(1);
return rightPath;
} else {
leftPath.set(0, leftPath.get(0) root.getLeftWeight());
leftPath.add(0);
return leftPath;
}
}
Here is how you could call it when you have a reference to a root node:
BinaryNode root;
// Construct the tree
// ... your code ...
//
// Get the heaviest path starting from the root
ArrayList<Integer> path = heaviestPath(root);
// Extract the weight of the path and output it
int weight = path.get(0);
path.remove(0);
System.out.println("Largest funness: " weight);
// Use the rest of the arraylist to walk along the path and print its node labels
BinaryNode node = root;
for (int side : path) {
System.out.println("Node: " node.getLabel());
if (side == 1) {
node = node.getRightChild();
} else {
node = node.getLeftChild();
}
}