[FIXED] How to implement a lambda within a depth first function

Issue

I'm programming a family tree, and I was instructed to use lambda in the depth first search. I've tried to implement it, and I understand the basics of lambdas. I can't for the life of me understand how to make it work with the instructions I was getting from the teacher. Here is how I've tried to apply the code.

void depthFirst(const std::function<void(Node* )>& node) {
    auto traverse = [](Node* node) {
        node(this);
        for( auto search: Person) {
            search->depthFirst(node);
        }
    };
}

    template<typename T>
    class Node {
    
    public:
        explicit Node(const T& data, Node* parent = nullptr) : data_(data), parent_(parent) {}
        explicit Node(T data): data_(std::move(data)) {}
        virtual ~Node() = default;
    
        T getData() const {
            return data_;
        }
        void setData(T data) {
            data_ = data;
        }
    
        Node *getParent() const {
            return parent_;
        }
        void setParent(Node *parent) {
            parent_ = parent;
        }
    
        bool leftExists() {
            return this->left_ != nullptr;
        }
        void setLeft(const std::unique_ptr<Node> &left) {
            left_ = left;
        }
        const std::unique_ptr<Node> &getLeft() const {
            return left_;
        }
    
        bool rightExists() {
            return this->right_ != nullptr;
        }
        const std::unique_ptr<Node> &getRight() const {
            return right_;
        }
        void setRight(const std::unique_ptr<Node> &right) {
            right_ = right;
        }
    
    private:
        T data_; // node's data value with use of template
    
        Node *parent_; // pointer to point at the parent node
        std::unique_ptr<Node> left_;
        std::unique_ptr<Node> right_;
    
    };
    
      

  
    template<typename T>
    class Person {
    public:
    
        Person();
        Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive);
    
        // setters
        void setFirstName(const std::string &firstName);
        void setLastName(const std::string &lastName);
        void setGender(const std::string &gender);
        bool isAlive() const;
        void setAlive(bool alive);
        void setAge(int age);
        void setPerson();
    
        // getters
        const std::string& getFirstName() const;
        const std::string& getLastName() const;
        const std::string& getGender() const;
        int getAge() const;
        bool getAlive() const;
    
    
        //operators
        void displayPerson()const; // for testing atm
    
        void setPerson(const Person& Person);
    
    private:
        std::string firstName_;
        std::string lastName_;
        int age_{};
        std::string gender_;
        bool alive_ = true;
    };
    
    // Functions that sets the data for the Person --->
    template<typename T>
    void Person<T>::setFirstName(const std::string &firstName) {
        firstName_ = firstName;
    }
    template<typename T>
    void Person<T>::setLastName(const std::string &lastName) {
        lastName_ = lastName;
    }
    template<typename T>
    void Person<T>::setGender(const std::string &gender) {
        gender_ = gender;
    }
    template<typename T>
    bool Person<T>::isAlive() const {
        return alive_;
    }
    template<typename T>
    void Person<T>::setAge(int age) {
        age_ = age;
    }
    template<typename T>
    void Person<T>::setAlive(bool alive) {
        alive_ = alive;
    }
    
    // This is the default constructor, overload constructor and destructor for the person class --->
    template<typename T>
    Person<T>::Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive) :
            firstName_(std::move(firstName)), lastName_(std::move(lastName)), age_(age), gender_(std::move(gender)), alive_(alive) {}
    template<typename T>
    Person<T>::Person() {
    }
    
    
    // Functions that gets the data for the Person --->
    template<typename T>
    int Person<T>::getAge() const {
        return 0;
    }
    template<typename T>
    const std::string &Person<T>::getFirstName() const {
        return this->firstName_;
    }
    template<typename T>
    const std::string &Person<T>::getLastName() const
    {
        return this->lastName_;
    }
    template<typename T>
    const std::string &Person<T>::getGender() const
    {
        return this->gender_;
    }
    template<typename T>
    bool Person<T>::getAlive() const {
        return false;
    }


    template<typename T> 
    class FamilyTree
    {
    public:
        FamilyTree();
        explicit FamilyTree(Node<T>* root); // Create new tree
        FamilyTree(T data):
    
    /*
        void addNewPerson();
        void addFather();
        void addMother();
    */
    
        void addNode(T data);
        bool isEmpty();
    
    private:
        Node<T> *root_;
        void addNode(Node<T>* root, T data);
    };
    
    template<typename T>
    FamilyTree<T>::FamilyTree(Node<T> *root) {
        this->root_ = root;
    }
    
    template<typename T>
    bool FamilyTree<T>::isEmpty() {
        return this->root_ == nullptr;
    }
    
    template<typename T>
    FamilyTree<T>::FamilyTree() {
        this->root_ = nullptr;
    }
    
    template<typename T>
    void FamilyTree<T>::addNode(T data) {
        if(root_ == nullptr)
            root_ = std::make_unique(Node<T>(data));
        else
            addNode(root_, data);
    }

//main

//just for test

void Person::displayPerson() const {
    std::cout << "First Name: " << this->getFirstName() << std::endl;
    std::cout << "Last Name: " << this->getLastName() << std::endl;
    std::cout << "Age: " << this->getAge() << std::endl;
    std::cout << "Gender: " << this->getGender() << std::endl;
    std::cout << "Alive: " << this->getAlive() << std::endl << std::endl;
}

    //main
    int main(){
    
            
            
        
            // Node test
            Node node;
        
            Node* setLeft(reinterpret_cast<Node *>(1));
            Node* setRight(reinterpret_cast<Node *>(2));
        
        
            std::cout << node.getData() << std::endl;
            std::cout << node.getLeft() << std::endl;
            std::cout << node.getRight() << std::endl;
        
        
            //Person test
            Person p0, p1("Robert", "Dane", 37, "Male", 1), p2("John", "Doe", 35, "Female", 1);
        
            p0.displayPerson();
            p1.displayPerson();
            p2.displayPerson();
        
        
            // FT test
        
            return 0;
        }
    
    void ignoreLine() // inspiration from here: https://stackoverflow.com/questions/11523569/how-can-i-avoid-char-input-for-an-int-variable
    {
        std::cin.clear();
        std::cin.ignore(INT_MAX, '\n');
    }
    
    void showMainMenu() // hold the output for the main menu
    {
        std::cout << "Welcome" << std::endl;
        std::cout << "Please enter a number for your choice below:\n" << std::endl;
        std::cout << "(1) Add new person to tree" << std::endl;
        std::cout << "(2) Show information for a person" << std::endl;
        std::cout << "(3) Print complete family-tree" << std::endl;
        std::cout << "(4) Used for testing new choices" << std::endl;
        std::cout << "(0) Quit" << std::endl;
        std::cout << "\nYour choice: " << std::endl;
    }
    
    int main()
    {
        familyTree fT; // used to access/init. familytree class.
    
        bool exit = true;
        int option;
    
        while (exit)
        {
            showMainMenu();
            std::cin >> option;
    
            while (std::cin.fail())
            {
                ignoreLine();
                std::cout << "\nOnly a number between 0 and 10 is allowed: ";
                std::cin >> option;
            }
    
            switch (option)
            {
                case 1:
                    fT.addNewPerson();
                    break;
                case 2:
                    std::cout << "Enter name of person to show information: ";
                    int temp;
                    std::cin >> temp;
                    fT.show(fT.search(temp));
                    break;
                case 3:
                    fT.printInOrder(fT.root, 0);
                    break;
                case 4:
                    /* n/a */
                    break;
                case 0:
                    exit = false;
                    break;
                default: ;
    
            }
            std::cout << "\nPress enter to continue.." << std::endl;
            ignoreLine();
        }
        return 0;

Old code that worked:

    person *familyTree::traverseLeft(person *ptr, const std::string& person)
    {
        ptr = ptr->left;
    
        while (ptr != nullptr)
        {
            if ((ptr->firstName) == person) {
                return ptr;
            }
    
            else if (traverseRight(ptr, person) != nullptr)
            {
                return traverseRight(ptr, person);
            }
            else
            {
                ptr = ptr->left;
            }
        }
        return nullptr;
    }
    
    person *familyTree::traverseRight(person *ptr, const std::string& person)
    {
    
        ptr = ptr->right;
    
        while (ptr != nullptr)
        {
            if ((ptr->firstName) == person)
            {
                return ptr;
            }
            else if (traverseLeft(ptr, person) != nullptr)
            {
                return traverseLeft(ptr, person);
            }
            else
                ptr = ptr->right;
        }
        return nullptr;

edit: The teacher told me that node(this); was supposed to point to the current node being searched. I may not have the most pedagogical correct teacher. But it is supposed to search the binary tree depth first, node for node. There is no use of vector or indexes, as I was told it was not needed. There is a class node and a class person that is implemented in to the node. If there is a better way of traversing a tree than this, feel free to let me know.

edited to add Person and Node.

edited to show old code that we got told to burn. I only got the instructions on lambda in person, but in short, was told to create lambda to use on a current node within a void function search, then go right, then go left. It could be reused in delete and other functions.

edited to add last of all code. Should I just go back to the old code (but less OOP) that I know compile and works? I got so much bad reviews on the old one that my group decided to start a new. But right now it's just a mess. (Keep in mind that the "new" code now is on different header files, so it might be more messy in regards to the console and main)

Solution

You're thinking inside out or upside down - you should pass a lambda (or another function) to this function, and this should apply that function in a depth-first manner.

You also need a helper function that takes a Node* that indicates the current node.

A very simple example, with a preorder traversal:

private:

void traverse(const std::function<void(Node*)>& action, Node* current) 
{
    if (current != nullptr)
    {
        action(current);
        traverse(action, current->getLeft());
        traverse(action, current->getRight());
    }
}

public:

void traverse(const std::function<void(Node*)>& action)
{
    traverse(action, root_); 
} 

And you are supposed to use it something like this:

FamilyTree tree = ... whatever ...;
auto process = [](const Node* p) { ... print p ... };
// This will now print in preorder.
tree.traverse(process);

Answered By - molbdnilo

Answer Checked By - Terry (PHPFixing Volunteer)

Read More

[FIXED] How to solve problem with binary tree print

Issue

I did a code that take as input integers, for example: 123 11 200 1 100 150 2000 and need to output a binary tree, in this form:

      ┌1
   ┌11┤
   │  └100
123┤
   │   ┌150
   └200┤
       └2000

but in my code output is:

0┐
 │      ┌1 
 │   ┌11┤
 │   │  └100 
 └123┤
     │   ┌150 
     └200┤
         └2000

At he root appear a zero and I do not know why. This is my code. I consider that the problem is in the add() method, but do not know how to solve it. I will be grateful for help.

    public class TreeNode extends BinaryTree implements PrintableTree {
    private int i;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int i) {
        this.i = i;
    }

    public TreeNode() {

    }

    @Override
    public void add(int i) {
        if (i > this.i) {
            if (this.rightChild == null) {
                this.rightChild = new TreeNode(i);
            } else {
                this.rightChild.add(i);
            }
        } else {
            if (this.leftChild == null) {
                this.leftChild = new TreeNode(i);
            } else {
                this.leftChild.add(i);
            }
        }
    }

    public int getI() {
        return i;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }



    @Override
    public String prettyPrint() {

        StringBuilderPlus builder = new StringBuilderPlus();
        prettyPrint(builder, "", "", "", "");

        return builder.toString();
    }

   public void print() {
       StringBuilderPlus res = new StringBuilderPlus();
       prettyPrint(res, "", "", "", "");
    }

    public void prettyPrint(StringBuilderPlus result, String prefix, String left, String mid, String right) {
        String indent = " ".repeat(String.valueOf(i).length());
        if (leftChild != null) {
            leftChild.prettyPrint(result, prefix + left + indent, " ", "┌", "│");
        }
        result.appendLine(prefix + mid + i
                + " ┐┘┤".charAt((leftChild != null ? 2 : 0)
                + (rightChild != null ? 1 : 0)));
        if (rightChild != null) {
            rightChild.prettyPrint(result, prefix + right + indent, "│", "└", " ");
        }
    }
}
public class StringBuilderPlus {

    private StringBuilder sb;

    public StringBuilderPlus(){
        sb = new StringBuilder();
    }

    public void append(String str)
    {
        sb.append(str != null ? str : "");
    }

    public void appendLine(String str)
    {
        sb.append(str != null ? str : "").append(System.getProperty("line.separator"));
    }

    public String toString()
    {
        return sb.toString();
    }
}
class BinaryTree {
    private TreeNode root;

    public void Print() {
        if (root != null) {
            root.print();
        }
    }

    public void add(int i) {
        if (root == null) {
            root = new TreeNode(i);
        } else {
            root.add(i);
        }
    }
}
public interface PrintableTree {

    void add(int i);
    String prettyPrint();

    static PrintableTree getInstance() {
        return new TreeNode();
    }
}

Solution

Thank you for posting the rest of the code. Your issue is with the PrintableTree interface in method getInstance. You return a new TreeNode (it comes initialized with 0 as int is a primitive type and cannot be null). And then you add the rest of the nodes to that original node with 0. You most likely wanted to return a new BinaryTree instead. However you need to change your code as BinaryTree does not implement the PrintableTree interface.

Here are the changes necessary to fix it:

In PrintableTree.java

static PrintableTree getInstance() {
    return new BinaryTree();
}

In BinaryTree.java

// notice the added implements
class BinaryTree implements PrintableTree {
// the rest of the class is fine, add this to the end
    @Override
    public String prettyPrint() {
        if (root != null) {
            return root.prettyPrint();
        }
        return "";
    }
}

Also the class TreeNode does not need to extend BinaryTree as a node is not a tree (it doesn't make sense for the node the contain a value AND a root). If your assignment requires this relation then edit the code accordingly.

Answered By - kravchenkoa

Answer Checked By - Mary Flores (PHPFixing Volunteer)

Read More

[FIXED] How to print binary tree diagram in Java?

Issue

How can I print a binary tree in Java so that the output is like:

   4 
  / \ 
 2   5 

My node:

public class Node<A extends Comparable> {
    Node<A> left, right;
    A data;

    public Node(A data){
        this.data = data;
    }
}

Solution

I've created simple binary tree printer. You can use and modify it as you want, but it's not optimized anyway. I think that a lot of things can be improved here ;)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTreePrinterTest {

    private static Node<Integer> test1() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(3);
        Node<Integer> n24 = new Node<Integer>(6);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);
        Node<Integer> n34 = new Node<Integer>(5);
        Node<Integer> n35 = new Node<Integer>(8);
        Node<Integer> n36 = new Node<Integer>(4);
        Node<Integer> n37 = new Node<Integer>(5);
        Node<Integer> n38 = new Node<Integer>(8);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;
        n12.left = n23;
        n12.right = n24;

        n21.left = n31;
        n21.right = n32;
        n22.left = n33;
        n22.right = n34;
        n23.left = n35;
        n23.right = n36;
        n24.left = n37;
        n24.right = n38;

        return root;
    }

    private static Node<Integer> test2() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(9);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;

        n12.right = n23;
        n22.left = n31;
        n22.right = n32;

        n23.left = n33;

        return root;
    }

    public static void main(String[] args) {

        BTreePrinter.printNode(test1());
        BTreePrinter.printNode(test2());

    }
}

class Node<T extends Comparable<?>> {
    Node<T> left, right;
    T data;

    public Node(T data) {
        this.data = data;
    }
}

class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                System.out.print(node.data);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}

Output 1 :

         2               
        / \       
       /   \      
      /     \     
     /       \    
     7       5       
    / \     / \   
   /   \   /   \  
   2   6   3   6   
  / \ / \ / \ / \ 
  5 8 4 5 8 4 5 8 

Output 2 :

       2               
      / \       
     /   \      
    /     \     
   /       \    
   7       5       
  / \       \   
 /   \       \  
 2   6       9   
    / \     /   
    5 8     4   

Answered By - michal.kreuzman

Answer Checked By - Robin (PHPFixing Admin)

Read More

[FIXED] How to update pointers when pushed on to std::stack using iteration?

Issue

Here is the situation:

Given a pointer to the root of a binary search tree(of integers) root and an integer data, perform the rotate function (predefined) on all the ancestral nodes of the node containing data using iterative method. For simplicity, assume data exists and always occurs on the leaf nodes.

The rotate function passes the pointer by reference as follows:

struct Node
{
    Node *left;
    int data;
    Node *right;
};

void rotate(Node* &root); // performs some rotation on the root and reflects the change.

void search(Node* &root, int data)
{
    stack<Node*> s;
    while(root->data!=data)
    {
        s.push(root);
        if(data<root->data)
            root=root->left;
        else
            root=root->right;
    }

    while(!s.empty())
    {
        rotate(s.top()); // does not reflect changes to root
        s.pop();
    }
}

The iterative version requires the use of a stack. std::stack::push() function pushes the pointer by value. As a result, while popping the ancestral pointers, I would be reflecting changes in the stack instead.

What is the best work around for this situation?

Solution

This solves my problem.

void search(Node* &root, int data)
{   
    if(root->data==data)
        return;

    stack<Node**> s;
    while(root->data!=data)
    {
        if(data<root->data)
        {
            s.push(&root->left);
            root=root->left;
        }
        else
        {
            s.push(&root->right);
            root=root->right;
        }
    }
    s.pop(); // to avoid leaf
    while(!s.empty())
    {
        rotate(*s.top())
        s.pop();
    }
    rotate(root);
}

Answered By - DoubtExpert

Answer Checked By - Willingham (PHPFixing Volunteer)

Read More

[FIXED] How to convert a list of edges to a tree in python?

Issue

I am having a list of edges that has the following format:

edges=[[1,4],[1,3],[1,2],[3,5],[3,6],[3,7]]

Here in each edge the first element is the parent node and the second is a child node i.e, in

[1,4]---->(1 is the parent node and 4 is child node)

I have to create a function that returns the pointer to the root of the tree. At first I tried creating a dictionary but after creating I am unable to proceed.

Please provide any ideas of how to implement this? Thanking you in advance

Solution

There are many ways to create a tree data structure... moreover Python does not have a pointer data type, so the root of a tree would be an object.

Here is one way to do it:

First define a Node class:

class Node():
    def __init__(self, data=None):
        self.data = data
        self.children = []

Then the main algorithm:

def create_tree(edges):
    # Get all the unique keys into a set
    node_keys = set(key for keys in edges for key in keys)
    # Create a Node instance for each of them, keyed by their key in a dict:
    nodes = { key: Node(key) for key in node_keys }
    # Populate the children attributes from the edges
    for parent, child in edges:
        nodes[parent].children.append(nodes[child])
        # Remove the child from the set, so we will be left over with the root
        node_keys.remove(child)
    # Get the root from the set, which at this point should only have one member
    for root_key in node_keys:  # Just need one
        return nodes[root_key]

Run it as follows:

# Example run
edges = [[1,4],[1,3],[1,2],[3,5],[3,6],[3,7]]
root = create_tree(edges)

If you want to quickly verify the tree's shape, add this method to the Node class:

    def __repr__(self, indent=""):
        return (indent + repr(self.data) + "\n"
                + "".join(child.__repr__(indent+"  ") 
                          for child in self.children))

And use it to print the tree:

print(root)

This print method is just a very simple way to visualise the tree. With a bit more code you can also draw the branches of the tree, but this is enough to debug the code.

Answered By - trincot

Answer Checked By - Cary Denson (PHPFixing Admin)

Read More

[FIXED] How to wrap vanilla javascript functions to reactjs without major modifications

Issue

This is part of my migration job from vanilla javascript to reactjs

export const WTree = () => {


    function Tree() {
        this.root = null;
    }


    

Read More